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=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.107.21.132 with SMTP id 126mr5055212iov.134.1510451454992; Sat, 11 Nov 2017 17:50:54 -0800 (PST) X-Received: by 10.157.95.5 with SMTP id f5mr530140oti.9.1510451454852; Sat, 11 Nov 2017 17:50:54 -0800 (PST) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!news.swapon.de!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!m191no900248itg.0!news-out.google.com!193ni5004iti.0!nntp.google.com!m191no900245itg.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sat, 11 Nov 2017 17:50:54 -0800 (PST) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=2601:191:8303:2100:5985:2c17:9409:aa9c; posting-account=fdRd8woAAADTIlxCu9FgvDrUK4wPzvy3 NNTP-Posting-Host: 2601:191:8303:2100:5985:2c17:9409:aa9c References: User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Standard Set types don't support a feature From: Robert Eachus Injection-Date: Sun, 12 Nov 2017 01:50:54 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Xref: feeder.eternal-september.org comp.lang.ada:48827 Date: 2017-11-11T17:50:54-08:00 List-Id: On Sunday, October 29, 2017 at 2:27:51 PM UTC-4, Dmitry A. Kazakov wrote: > > Well, maybe all it is a preliminary optimization. Maybe regular (non-sp= arse) > > incidence matrix will be not slower. Definitely a situation where early optimization is the enemy of good code. > Rather faster, considering 2D Boolean array. A true transitive connection matrix (assuming it is large enough to matter)= may be stored as a triangular matrix. (T(I,J) =3D T(J,I).) Another option= , again once you have the code working, is to have a one dimensional vector= where each entry is an integer and if I and J are members of the same clos= ure, TC(I)=3DTC(J) otherwise they are not connected. There is a neat (but = single threaded*) algorithm for generating the vector. Start with a vector= of all zeroes. Choose the first row of your transitive closure matrix whe= re TC(I) is zero and set all members of the vector where the array values T= (I,J) are equal to one, to I. When you are finished you will have an inte= ger vector that collapses the two dimensional Boolean array. Will it be faster for your purposes? Depends on the sparsity of the transit= ive closure, and how many lookups you will be doing. Will it be more compa= ct than a list of ordered pairs? Always. (Unless the array is very sparse,= and you don't store identity pairs.) * If you are working with a very large array, supercomputer sized, there is= a speedup available. Divide the transitive closure into multiple (square)= blocks. You will need to do this to store it anyway. Now once a thread f= inishes with the first block, you can start a new thread in that block. Wh= en finished with that block start on the next diagonal block, same rules. = (The algorithm can be modified to compute the transitive closure in O(n) ti= me, given the original matrix as a (sorted) list of ordered pairs. But cre= ating that list can dominate the computation time.)