#15931: Implement a proper hash function for (combinatorial) free module
elements
-----------------------+----------------------------------
Reporter: nthiery | Type: defect
Status: new | Priority: major
Milestone: sage-6.2 | Component: linear algebra
Resolution: | Report Upstream: N/A
-----------------------+----------------------------------
Up to now, CombinatorialFreeModule elements used the (horrible)
default implementation of __hash__ provided by Element which uses the
string representation. This was slow! And further fragile! Indeed, the
string representation depends on a sorting of the support of the
elements. In #14102 we got bitten by this with elements whose support
mixed int's, Integer's and string. The result of:
{{{
sage: sorted([int(0), 'delta', 1])
[0, 1, 'delta']
}}}
depends on the platform (that's ok) but also on which of 0 and 1 are
int's or Integer, whereas the corresponding lists test as equal.
This led to equal element with distinct hash values.
This ticket adds an implementation of `__hash__` inspired from that
proposed for frozendicts in PEP 0416. In particular this
implementation does not rely on sorting.
Some timings:
{{{
sage: F = CombinatorialFreeModule(QQ, ['a','b','c'])
sage: B = F.basis()
sage: f = B['a'] + 3*B['c']
sage: %timeit hash(f) # new hash function
100000 loops, best of 3: 3.57 µs per loop
sage: %timeit hash(f._repr_()) # equivalent to the
previous one
10000 loops, best of 3: 85 µs per loop
}}}
There used to be a custom hash function for ambient space elements in
root systems, but this is not needed anymore:
{{{
sage: F = RootSystem(['A',2]).ambient_space()
sage: f = F.simple_root(0)
sage: %timeit hash(f) # new hash function
100000 loops, best of 3: 3.63 µs per loop
sage: %timeit hash(f._repr_()) # equivalent to the
previous one
10000 loops, best of 3: 42.3 µs per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/15931>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
