ANN: equivalence 0.1
Giuseppe Ottaviano
giuott at gmail.com
Mon Jun 2 12:31:07 CEST 2008
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
More information about the Python-list
mailing list