#13501: Bugs in C3'salgorithm implementation in sage.misc.c3
-------------------------------------------+--------------------------------
Reporter: nthiery | Owner: nthiery
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.4
Component: categories | Resolution:
Keywords: method resolution order | Work issues:
Report Upstream: N/A | Reviewers: Simon King
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: #12895 | Stopgaps:
-------------------------------------------+--------------------------------
Changes (by {'newvalue': u'Nicolas M. Thi\xe9ry', 'oldvalue': ''}):
* status: new => needs_review
* reviewer: => Simon King
* author: => Nicolas M. Thiéry
Comment:
Hi!
I optimized and cleaned a bit the code; here are some timings, using the
following for benchmarking (better suggestions welcome):
{{{
sage: l = GradedHopfAlgebrasWithBasis(GF(3)).all_super_categories() # to
force preloading everything
sage: def f(n):
... for i in range(5,n+5):
... GradedHopfAlgebras(GF(nth_prime(i))).all_super_categories()
}}}
Before:
{{{
sage: %prun f(200)
...
2800/200 0.189 0.000 1.298 0.006 {sage.misc.c3.C3_algorithm}
}}}
With [attachment:trac_13501-categories-c3_fix-nt.patch]:
{{{
sage: %prun f(200)
...
2800/200 0.249 0.000 1.430 0.007 {sage.misc.c3.C3_algorithm}
}}}
With further [attachment:trac_13501-categories-c3_fix-
useless_optimization-nt.patch]:
{{{
sage: %prun f(200)
...
2800/200 0.249 0.000 1.429 0.007 {sage.misc.c3.C3_algorithm}
}}}
So, we have a 15% loss compared to the previous implementation. I am
not sure exactly where it's slower, but I guess it's just the price
for correctness (the previous implementation was popping out stuff too
early). As the second attachment shows, using PyList_GET_ITEM and
friends does not seem to bring anything substantial, so I'd vote for
sticking to more readable Python notations.
'''Apply''':
* [attachment:trac_13501-categories-c3_fix-nt.patch]
Simon: let me know in case you are busy, I can possibly ask Florent for
the review.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13501#comment:3>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
