Re: Standard Set types don't support a feature

[Robert Eachus <rieachus@comcast.net>]

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-sparse)
> > 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) = 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 closure, TC(I)=TC(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 where 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 integer vector that collapses the two dimensional Boolean array.

Will it be faster for your purposes? Depends on the sparsity of the transitive closure, and how many lookups you will be doing.  Will it be more compact 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 finishes with the first block, you can start a new thread in that block.  When 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) time, given the original matrix as a (sorted) list of ordered pairs.  But creating that list can dominate the computation time.)