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,FREEMAIL_FROM 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.80.168 with SMTP id s8mr906891pax.28.1342917237459; Sat, 21 Jul 2012 17:33:57 -0700 (PDT) Path: p10ni26741273pbh.1!nntp.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!novia!news-peer1!btnet!zen.net.uk!hamilton.zen.co.uk!xlned.com!feeder5.xlned.com!feed.xsnews.nl!border-1.ams.xsnews.nl!plix.pl!newsfeed2.plix.pl!news.mi.ras.ru!goblin1!goblin.stu.neva.ru!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Keean Schupke Newsgroups: comp.lang.ada Subject: Re: Efficient Sequential Access to Arrays Date: Mon, 16 Jul 2012 23:40:21 -0700 (PDT) Organization: http://groups.google.com Message-ID: <9b134675-b217-4a62-beb1-8b044029aa61@googlegroups.com> References: <4c86d54d-dfeb-44f1-9638-3c416ea51d74@googlegroups.com> NNTP-Posting-Host: 82.44.19.199 Mime-Version: 1.0 X-Trace: posting.google.com 1342507343 18897 127.0.0.1 (17 Jul 2012 06:42:23 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Tue, 17 Jul 2012 06:42:23 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=82.44.19.199; posting-account=T5Z2vAoAAAB8ExE3yV3f56dVATtEMNcM User-Agent: G2/1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Date: 2012-07-16T23:40:21-07:00 List-Id: On Monday, 16 July 2012 23:23:34 UTC+1, (unknown) wrote: > I'm confused. The Subject line here is "Efficient Sequential Ac= cess to Arrays" > and you gave a sample piece of code > > for J in S .. E loop > > Y :=3D Y + X(J).Z; > > end loop; > and mentioned stepping through X with a pointer rather than an index. >=20 > 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 t= here > 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&q= uot; memory > addresses. Look for example at the connected points example, or the Percolation exampl= e, or the hex game example. There are problems where the connectedness of s= ubsets is only one part of the problem. In this case connectedness is one p= art, and spatial proximity is another. >=20 > ----------- > As to > > for J in S .. E loop > > Y :=3D 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 :=3D (others=3D>0); > for i in X'range loop > X_Grouped(i/Group_Size) :=3D X_Grouped(i/Group_Size) + X(i); > end loop; >=20 > then instead of summing N =3D (E-S+1) X's, you can sum X_Grouped fr= om > 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 t= he 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 quickl= y found (using indexed-addressing), another is that we need to be able to t= ell if any two elements are in the same group (using disjoint-set union-fin= d), and another is that we need to be able to iterate through all the membe= rs 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. =20 Cheers, Keean.