From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,56525db28240414a
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.66.86.232 with SMTP id s8mr232317paz.47.1342778523858;
        Fri, 20 Jul 2012 03:02:03 -0700 (PDT)
MIME-Version: 1.0
Path: 
 p10ni13423331pbh.1!nntp.google.com!border1.nntp.dca.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!novia!news-hub.siol.net!news.mi.ras.ru!goblin2!goblin.stu.neva.ru!aioe.org!.POSTED!not-for-mail
From: tmoran@acm.org
Newsgroups: comp.lang.ada
Subject: Re: Efficient Sequential Access to Arrays
Date: Mon, 16 Jul 2012 22:23:34 +0000 (UTC)
Organization: Aioe.org NNTP Server
Message-ID: <ju2496$988$1@speranza.aioe.org>
References: <4c86d54d-dfeb-44f1-9638-3c416ea51d74@googlegroups.com>
NNTP-Posting-Host: Lf0Nl3CcQzx+ocHx9cmuGg.user.speranza.aioe.org
X-Complaints-To: abuse@aioe.org
X-Notice: Filtered by postfilter v. 0.8.2
X-Newsreader: Tom's custom newsreader
Date: 2012-07-16T22:23:34+00:00
List-Id: <comp.lang.ada>

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.

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