Re: Efficient Sequential Access to Arrays

[Keean Schupke <keean.schupke@googlemail.com>]

On Monday, 16 July 2012 23:23:34 UTC+1, (unknown)  wrote:
> I'm confused.  The Subject line here is "Efficient Sequential Access to Arrays"
> and you gave a sample piece of code
> >  for J in S .. E loop
> >      Y := Y + X(J).Z;
> >  end loop;
> and mentioned stepping through X with a pointer rather than an index.
> 
>   But now you are talking about algorithms mentioned in
> >  http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
>   which have to do with nodes connected in a graph.  I'm not seeing there
> anyplace where the relation between a(i) and a(i+1) is different from the
> relation between a(i) and a(i+anything) - each node is independent and
> may be connected to any other node, not just to those with "nearby" memory
> addresses.

Look for example at the connected points example, or the Percolation example, or the hex game example. There are problems where the connectedness of subsets is only one part of the problem. In this case connectedness is one part, and spatial proximity is another.

> 
>    -----------
> As to
> >  for J in S .. E loop
> >      Y := Y + X(J).Z;
> >  end loop;
>   if S and E are random and typically fairly far apart, and the array
> X remains constant, how about grouping Xs, eg
>   X_Grouped := (others=>0);
>   for i in X'range loop
>     X_Grouped(i/Group_Size) := X_Grouped(i/Group_Size) + X(i);
>   end loop;
> 
>   then instead of summing N = (E-S+1) X's, you can sum X_Grouped from
> S/Group_Size .. E/Group_Size, which takes 1/Group_Size as many array
> access and adds, and then handle the partial groups at the ends, which
> will take 2*(Group_Size/2) operations on average.  So instead of
> N sums on average, you will have N/Group_Size + Group_Size.  (Handling
> the partial groups at the ends more carefully also cuts that second
> term in half.)

This example was supposed to be a simple way to show the compiler does not optimise the multiply out of each array access, and it does not represent the actual problem.

The real problem is that each element needs to be addressed spatially (say as a 2D grid) so that all 4 direct, and 4 diagonal neighbours can be quickly found (using indexed-addressing), another is that we need to be able to tell if any two elements are in the same group (using disjoint-set union-find), and another is that we need to be able to iterate through all the members of a group given any element in that group.

If there is a faster data structure that meets all those requirements, then I am listening.

    
Cheers,
Keean.