G
George Sakkis
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.
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.