Re: Efficient Sequential Access to Arrays

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Mon, 16 Jul 2012 23:40:21 -0700 (PDT), Keean Schupke wrote:

> 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.

Depends on details.

k-d trees might be worth looking.

Less known are "pyramid" structures (used in image processing, filtering,
compression).

For image segmenting, e.g. by area growing (8th-neighbourhood), one
sometimes uses recursive elements permutations like (1,1) (1,2) (2,1) (2,2)
(1,3) (1,4) (2,3) (2,4). That allows to perform segmenting in strictly
consequent order visiting each pixel once. I remember it was popular in
PDP-11 days when integer multiplication was indeed expensive.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de