ANN: equivalence 0.2

George Sakkis george.sakkis at gmail.com
Tue Jun 3 22:02:03 EDT 2008


Equivalence v0.2 has been released. Also the project is now hosted at
http://code.google.com/p/pyquivalence/ (the name 'equivalence' was
already taken but the module is still called equivalence).

Changes
=======
- The internals were largely rewritten, but the API remained
effectively intact.
- A new `equivalence(**kwds)` factory function is now the preferred
way to create an equivalence. Two kwds supported for now, `key` and
`bidirectional`.
- Now uses the union-find algorithm on disjoint-set forests; improves
the linear worst-case time to practically constant amortized time for
the basic operations.
- Modular redesign; the original Equivalence class has been broken
down into subclasses, each trading off more features with extra
overhead:
  - The base Equivalence class is a vanilla disjoint-sets forest; it
doesn't support keys and partition() is slow, but the rest operations
are faster.
  - KeyEquivalence adds implicit (key-based) equivalence.
  - BidirectionalEquivalence provides fast partition() at the cost of
higher memory overhead and slowing down slightly the rest operations.
  - KeyBidirectionalEquivalence combines the two previous.
- Added more tests and updated docs.

About
=====
*equivalence* is a Python module for building equivalence relations:
partitionings of objects into sets that maintain the equivalence
relation properties (reflexivity, symmetry, transitivity). Two objects
are considered equivalent either explicitly, after being merged, or
implicitly, through a key function.



More information about the Python-list mailing list