#13501: Fix two bugs in sage.misc.c3's implementation of the algorithm C3
-------------------------------------------------+--------------------------
Reporter: nthiery | Owner:
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, Simon King | Merged in:
Dependencies: #12895 | Stopgaps:
-------------------------------------------------+--------------------------
Comment (by SimonKing):
The following "raw data" should give an advise what syntax to use.
I defined
{{{
include "sage/ext/python_list.pxi"
def test1(list L, object O):
cdef set S
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
S = <set>PyList_GET_ITEM(L,i)
b = <size_t><void *>O in S
def test2(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = <size_t><void *>O in <set>PyList_GET_ITEM(L,i)
def test3(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = <size_t><void *>O in <set>L[i]
def test4(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = id(O) in <set>L[i]
def test5(list L, object O):
cdef size_t i
cdef size_t l = len(L)
cdef bint b
for i from 0<=i<l:
b = id(O) in <set>PyList_GET_ITEM(L,i)
}}}
and obtain
{{{
sage: L = [set(id(GF(p)) for p in prime_range(n,n+500)) for n in
range(1,1000)]
sage: O = GF(next_prime(500))
sage: timeit("test1(L,O)", number=2000)
2000 loops, best of 3: 48.9 µs per loop
sage: timeit("test2(L,O)", number=2000)
2000 loops, best of 3: 45.7 µs per loop
sage: timeit("test3(L,O)", number=2000)
2000 loops, best of 3: 70.9 µs per loop
sage: timeit("test4(L,O)", number=2000)
2000 loops, best of 3: 107 µs per loop
sage: timeit("test5(L,O)", number=2000)
2000 loops, best of 3: 87.1 µs per loop
}}}
So, I would say that it really matters whether or not we should do
`<set>PyList_GET_ITEM(L,i)` or `<set>L[i]` (see test2 versus test3), and
it also matters whether we do `<size_t><void *>O` or `id(O)` (see test3
versus test4 and test2 versus test5). Assigning to a temporary variable is
not good (unless we need the same set twice, of course).
Seeing these data, I think a syntax as in test2 is best. Sure, C3 does
more than an element test in a list of sets. But I do think it is a
critical step.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13501#comment:25>
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.
