finding 1d index in 2d array of indices
Author Message
finding 1d index in 2d array of indices

It has turned out that my search spaces, that we assumed to be roughly
eliptical, look more like sideways tornados (with 2 dimensions.  I think
the 4D will hurt :)

I have a sequence of starting points, and bubbles in n-space about them.
These bubbles are represented by an array of dimension n with size
BUBSIZE in all directions.  (ie, -2:2,-2:2, for N=2,BUBSIZE=5)

No machine yet made could allocate the bubbles for the entire search
space, so I allocate around my starting points, and add them as needed.
But I need to be able to find them again . . .

I'm planning on an array of BUBCENTERS, which will be two dimensional--
the centers in the first, with the second as an index.  I then need
to, very rapidly (this is a chokepoint), find the I for which
BUBINDEX=BUBCENTERS(:,i).

I'm using F90, not F95

I can produce BUBINDEX with the line

bubindex= (lcn+ubounds-modulo(lcn+ubounds,bubsize))

where ubounds is an integer (call it 2), and bubsize = 2*ubounds+1
lcn is an array of size N which tells the exact address sought.
(I don't just index the address; the nature of search means that once I
look at one, I'll need a group in it's vicinity, so the bubbles are
convenient and (I believe) efficient to hold groups of bubblettes [single
locations])

I then need to find I such
BUBCENTERS(:,I) .eq. BUBINDEX

I could do this with a loop, of course, but I'm assuming that that will
be orders of magnitude slower than what the optimizer could do.

It seems to me that I should be able to do something of the effect of

myCenter = maxloc(BUBCENTERS(:,*).eq.bubIndex)
which would return the first index (which would be the only one) for
dimension 2 where the match occurs, and the 1 if there is no match
(though maybe I mean minloc(), i'm not clear at the moment whether
.true. or .false. is greater.

I also suppose that I could accomplish the same things with a stride
by breaking BUBCENTERS into four arrays, then looking for a match
in all 4, but I believe that this would also lose the optimizations.

Or perhaps swap indices, so that BUBCENTERS(:,dim) retrieves the
indices for dimension dim, and then multiply the N vectors from
BUBCENTERS(:,dim)-BUBINDEX(dim) ?

I don't see a reason that this wouldn't work, but the swapping of
dimensions makes me suspiciouse . . .

Ultimately, though, it is speed, not pretty, that matters here.

rick

--
These opinions will not be those of ISU until it pays my retainer.

Wed, 18 Jun 1902 08:00:00 GMT
finding 1d index in 2d array of indices
myCenter = maxloc(BUBCENTERS(:,*).eq.bubIndex)
which would return the first index (which would be the only one) for dimension 2 where the match occurs, ...

==========================================================
Well, that's not quite correct code. In the following, the intrinsic calls were faster than the DO construct, and maybe your data are such that you can dispense with the ABS:

integer, dimension(10,100000) :: b=5, j(1)
b(:,50000) = 2
call system_clock(it1,it0)
do i = 1, 100000
if(b(1,i) == 2) exit
end do
call system_clock(it2)
print *, i, real(it2-it1)/it0
call system_clock(it1)
j = minloc(abs(b(1,:)-2))
call system_clock(it2)
print *, j, real(it2-it1)/it0
end

Mike Metcalf
--

Wed, 18 Jun 1902 08:00:00 GMT
finding 1d index in 2d array of indices

Quote:
>>myCenter = maxloc(BUBCENTERS(:,*).eq.bubIndex)
>>which would return the first index (which would be the only one) for
>>dimension 2 where the match occurs, ...
>Well, that's not quite correct code.

I discovered that :)  I had assumed that maxloc() could be applied
to logicals, but the compiler says otherwise :(

Quote:
>In the following, the intrinsic calls were faster than the DO construct,
>and maybe your data are such that you can dispense with the ABS:

I can't dispense with it, as it can be postive or negative, and I'm
looking for a match.  But this is *exactly* what I need:

Quote:
>j = minloc(abs(b(1,:)-2))

well, most of it; I suppose I need to take the abs() of the difference,
then sum them, and take minloc() of the resulting vector.

But the more I think about it, the odder I find it that there is no
intrinsic to search non-strings . . .

Thank you greatly,

rick

--
These opinions will not be those of ISU until it pays my retainer.

Wed, 18 Jun 1902 08:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages