#15303: Coercion discovery fails to be transitive
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-5.13
Component: coercion | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues: Crash in permgroup.py
Branch: | Commit:
u/SimonKing/ticket/15303 | 807550bbc45e9872ac365fc98b817ccd5bcfbb95
Dependencies: #14711, #15329, | Stopgaps:
#15331 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Rather than `TripleDict`, one could also use a set (not a dict) and use
`id(X)` for comparison. It would compare the parents in the same way as
they are compared in the backtracking (namely by id), ''and'' it yields a
speed-up.
Here is my benchmark. I've put the following into `sage.structure.parent`:
{{{
#!python
def test_registration(list L):
_coerce_test_dict.clear()
for X in L:
for Y in L:
_register_pair(X,Y,"test")
_is_registered_pair(X,Y,"test")
_is_registered_pair(X,Y,"fail")
for X in L:
for Y in L:
_unregister_pair(X,Y,"test")
from sage.structure.coerce_dict cimport TripleDict
def test_tripledict(list L):
TestT = TripleDict(29)
for X in L:
for Y in L:
TestT.set(X,Y,"test",1)
(X,Y,"test") in TestT
(X,Y,"fail") in TestT
for X in L:
for Y in L:
del TestT[X,Y,"test"]
cdef set testset
def test_set(list L):
global testset
testset = set([])
for X in L:
for Y in L:
testset.add((id(X),id(Y),"test"))
(id(X),id(Y),"test") in testset
(id(X),id(Y),"fail") in testset
for X in L:
for Y in L:
try:
testset.remove((id(X),id(Y),"test"))
except KeyError:
pass
}}}
With this, I get
{{{
sage: L = [GF(p) for p in prime_range(10^4)]
sage: len(L)
1229
sage: from sage.structure.parent import test_registration,
test_tripledict, test_set
sage: %time test_registration(L)
CPU times: user 16.75 s, sys: 0.10 s, total: 16.85 s
Wall time: 16.87 s
sage: %time test_tripledict(L)
CPU times: user 45.74 s, sys: 0.62 s, total: 46.36 s
Wall time: 46.44 s
sage: %time test_set(L)
CPU times: user 3.92 s, sys: 0.00 s, total: 3.93 s
Wall time: 3.93 s
}}}
__Conclusion__
It is not a good idea to use a `TripleDict` here (because of speed and
because of potential trouble with garbage collection). However, using a
set makes sense for two reasons: Speed and consistency of the methods of
comparison. And it might be possible to get a further speed-up by doing
something like `<long><void*>X` rather than `id(X)`.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:87>
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/groups/opt_out.
