#6812: Enumerate integer vectors modulo to the action of a Permutation Group
------------------------------------------------------------------+---------
Reporter: nborie |
Owner: nborie
Type: enhancement |
Status: needs_review
Priority: major |
Milestone: sage-5.1
Component: combinatorics |
Resolution:
Keywords: enumeration, integer, list, permutation, group | Work
issues: long time tests, information about listing infinite sets
Report Upstream: N/A |
Reviewers: Karl-Dieter Crisman, Simon King
Authors: Nicolas Borie | Merged
in:
Dependencies: |
Stopgaps:
------------------------------------------------------------------+---------
Comment (by SimonKing):
When I see
{{{
for child in children:
if child not in new_to_analyse:
new_to_analyse.append(child)
}}}
in the cpdef function "orbit" in
sage.combinat.enumeration_mod_permgroup.pyx, it seems to me that
new_to_analyse should rather be a set, not a list, since the containment
test "child not in new_to_analyse" works a ''lot'' faster on (long) sets
than lists.
Create a relatively large set of random ints, and get the corresponding
list (unsorted, apparently):
{{{
sage: S = set(randint(1,20000) for _ in range(5000))
sage: L = list(S)
sage: L[:10]
[16384, 5019, 16203, 8195, 16388, 8197, 16391, 600, 16394, 8204]
}}}
Now, define one function operating on lists and another operating on sets
that add the integers from 0 to 10000 to the list or set - but only if it
isn't in the list/set yet.
{{{
sage: cython("""
....: def test1(list L):
....: cdef int i
....: for i in range(10000):
....: if i not in L:
....: L.append(i)
....: def test2(set S):
....: cdef int i
....: for i in range(10000):
....: S.add(i)
....: """)
sage: len(L)
4426
sage: %time test1(L)
CPU times: user 2.11 s, sys: 0.00 s, total: 2.12 s
Wall time: 2.12 s
sage: len(L)
12240
}}}
The operation on the set is so much faster that I'm measuring it with
timeit, also taking the time to copy the set (so that the length is
preserved when running the loop for the timing):
{{{
sage: len(S)
4426
sage: %timeit test2(copy(S))
625 loops, best of 3: 1.12 ms per loop
sage: len(S)
4426
}}}
Hence, the same operation (at least in my proof-of-concept) is roughly
2000 times faster on sets than on lists.
The disadvantage is that the output of orbit() would be in a random order,
so that to the very least it has to be sorted in the doc tests. Do you
want that the output of orbit() is a sorted list (which would of course
easy to implement)?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6812#comment:75>
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.
