ANN: equivalence 0.1

[Giuseppe Ottaviano]

On Jun 1, 2008, at 6:16 PM, George Sakkis wrote:

> Equivalence is a class that can be used to maintain a partition of
> objects into equivalence sets, making sure that the equivalence
> properties (reflexivity, symmetry, transitivity) are preserved. Two
> objects x and y are considered equivalent either implicitly (through a
> key function) or explicitly by calling merge(x,y).

I think this library would be very useful, and I like the interface  
(in particular the idea of the projecting function), but I think the  
algorithm is less than optimal. It can show quadratic behavior in some  
cases:

$ python -m timeit -s 'import equivalence' -s 'eq =  
equivalence.Equivalence()' 'for i in xrange(10000): eq.merge(i, i+1)'
10 loops, best of 3: 57.6 msec per loop

$ python -m timeit -s 'import equivalence' -s 'eq =  
equivalence.Equivalence()' 'for i in xrange(10000): eq.merge(i+1, i)'
10 loops, best of 3: 2.59 sec per loop

Have you considered using the Union-Find algorithm, which would be  
(almost) linear in all cases?

-- Giuseppe