#19016: A more naive sage.structure.element.__hash__
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_work
Type: | Milestone: sage-duplicate/invalid/wontfix
defect | Resolution:
Priority: | Merged in:
blocker | Reviewers:
Component: misc | Work issues:
Keywords: | Commit:
Authors: | 754dc5794a1a7004c8844cf7cfb64220957c36a5
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/19016 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by nbruin):
Replying to [comment:22 mmarco]:
> The problem is that we don't know, a priory, if a finitely presented
group is finite or not. And just trying to check it automatically can take
forever or exhaust the memory. That is why I proposed to go for the
abelianization, which is an invariant of the element that can be always
computed (and in a reasonably fast way). It still has some collisions, but
it is way better than having always a collision.
For finite simple groups I think "some collisions" is a bit of an
understatement, but that's not the main point. The thing is: for pretty
much any application of hashing, you will need equality testing too (this
is definitely the case in Python's dicts), and then Gap will just go off
and compute this stuff anyway, unless we go with Volker's suggestion of
inheriting equality (and hashing) from the free covering presentation.
So we should definitely only compute the hash function lazily, but if it's
asked for, I think we would incur a very small penalty in practice if we
replicate the logic from Gap's [https://github.com/gap-
system/gap/blob/master/lib/grpfp.gi#L236 MakeFpGroupCompMethod].
--
Ticket URL: <http://trac.sagemath.org/ticket/19016#comment:23>
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.
