#15931: Implement a proper hash function for (combinatorial) free module
elements
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.2
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Nicolas M. Thiéry | Reviewers: Florent Hivert
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/nthiery/ticket/15931 | a2bbe7f297caeb73bda1f8ce31af9ee21b90a26b
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by nthiery):
* cc: tscrim, aschilling, bump (added)
* status: positive_review => needs_work
Old description:
> 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
> }}}
New description:
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
}}}
See #15959 for a follow up.
--
Comment:
Changing the hash value of combinatorial free module elements changes the
order in which they get sorted when printing, e.g., sets. This causes a
bunch of trivial doctest failures that are not deterministic, in
particular in crystals and weyl character rings. I am in the process of
fixing those, trying at this occasion to make the tests more deterministic
when easy. Further work on making those tests deterministic would be
desirable in later tickets.
Also, for now, I removed the hash value of the parent from the hash value
of the elements. See #15959. Travis: please check it out!
Cheers,
--
Ticket URL: <http://trac.sagemath.org/ticket/15931#comment:14>
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.
