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
--
http://mail.python.org/mailman/listinfo/python-list
