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  
 
 [ 3 post ] 

 Relevant Pages 

1. convert 2d array to 1d array without using shift registers and build array

2. RubyChangeRequest #U002: new proper nameforHash#indexes, Array#indexes

3. RubyChangeRequest #U002: new proper namefor Hash#indexes, Array#indexes

4. 1D binairy array (I16) to 2D array

5. Change a 2D Array into a 1D Array.

6. 1d array containing means of a 2d array

7. 2D array to 1D array

8. finding name/index of checkbutton array in -command

9. Join 1D three arrays together become a 1d array

10. array 2D to 1D

11. Numeric and PIL: 1D array from 2D-tuple

12. Index Values of an Array inside a Cluster inside an Array

 

 
Powered by phpBB® Forum Software