Re: Efficient Sequential Access to Arrays

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

On Monday, 16 July 2012 20:43:54 UTC+1, John B. Matthews  wrote:
>  Keean Schupke wrote:
> 
> > > On Mon, 16 Jul 2012 03:16:09 -0700 (PDT), Keean Schupke wrote:
> > > 
> > > > On Monday, 16 July 2012 08:47:01 UTC+1, Dmitry A. Kazakov  wrote:
> > > > > On Sun, 15 Jul 2012 13:03:12 -0700 (PDT), Keean Schupke wrote:
> > > > >  
> > > > > Absolute figures tell little. How big is the relative difference?
> > > > 
> > > > About 25% (30k with indexing, 40k with relative addressing)
> > > 
> > > Which itself looks like a problem. It takes no less than 25% of 
> > > overall performance for mere shuffling data in a task unrelated to 
> > > stuff like recoding etc. This looks wrong to me. I would look for a 
> > > better algorithm/structure.
> > 
> > I find this comment puzzling and does not match my experience. What 
> > sort of algorithms do you work with. What algorithm for disjoint-set 
> > do you suggest I use? Have a read of this:
> > 
> > http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
> 
> Apropos to this, may I impose on you to elaborate on your previous 
> decision not to use WQUPC? In particular, is your application lookup 
> dominated due in some part to the choice of algorithm itself?
> 
> Sorry if I've overlooked an intervening clarification.
> 
> <https://groups.google.com/d/msg/comp.lang.ada/EDgDNVw9tgc/bUYu34D_8LEJ>
> 
> > Can you come up with a faster algorithm? Until you have read it I 
> > don't think you can comment on the quality of algorithm I am using.
> 
> -- 
> John B. Matthews
> trashgod at gmail dot com
> <http://sites.google.com/site/drjohnbmatthews>

That is correct, it is lookup dominated. By joining the smaller set to the lager set and updating the canonical pointer for each node in the smaller set at join time we get better performance for this particular problem.

The second part of the question is harder, is it lookup dominated due to the choice of algorithm? I don't think so. Certainly the choice of Eager-Union vs WUQPC has no influence on the number of lookups.

So the question then becomes what is the wider algorithm, what are we using the disjoint-set to do, but this is getting off topic. The original point was that there exist a class of algorithms for which array indexing is a non-optimal approach to accessing the container. There exists a class of algorithms that require both indexes and linked access within the same data structure, a linked-hash table for example.

So lets try and focus here: Given that such a class of algorithms exist, and for some problems will be optimal, how do we best implement them in Ada?


Cheers,
Keean.