#7415: improve cycle decomposition
------------------------------------------------+---------------------------
Reporter: ylchapuy | Owner: mhansen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-combinat
Component: combinatorics | Keywords: permutation
Work_issues: Speed regression for small input | Author: Yann
Laigle-Chapuy
Reviewer: Florent Hivert | Merged:
------------------------------------------------+---------------------------
Changes (by hivert):
* status: needs_review => needs_work
* reviewer: => Florent Hivert
* work_issues: => Speed regression for small input
Comment:
Replying to [comment:1 ylchapuy]:
> it can be slightly slower for small permutations with `singletons=False`
(because of the way we construct L), but I think it's worth it.
It is indeed in both cases:
Before
{{{
sage: for i in range(8): timeit('[p.to_cycles(True) for p in
Permutations(i)]')
....:
625 loops, best of 3: 16.5 µs per loop
625 loops, best of 3: 22.3 µs per loop
625 loops, best of 3: 41.3 µs per loop
625 loops, best of 3: 114 µs per loop
625 loops, best of 3: 450 µs per loop
125 loops, best of 3: 2.45 ms per loop
25 loops, best of 3: 15.8 ms per loop
5 loops, best of 3: 118 ms per loop
sage: for i in range(8): timeit('[p.to_cycles(False) for p in
Permutations(i)]')
....:
625 loops, best of 3: 32.4 µs per loop
625 loops, best of 3: 20.8 µs per loop
625 loops, best of 3: 39.3 µs per loop
625 loops, best of 3: 109 µs per loop
625 loops, best of 3: 441 µs per loop
125 loops, best of 3: 2.41 ms per loop
25 loops, best of 3: 15.4 ms per loop
5 loops, best of 3: 113 ms per loop
}}}
After:
{{{
sage: for i in range(8): timeit('[p.to_cycles(True) for p in
Permutations(i)]')
....:
625 loops, best of 3: 23.2 µs per loop
625 loops, best of 3: 26.3 µs per loop
625 loops, best of 3: 49.6 µs per loop
625 loops, best of 3: 136 µs per loop
625 loops, best of 3: 542 µs per loop
125 loops, best of 3: 2.9 ms per loop
25 loops, best of 3: 18.1 ms per loop
5 loops, best of 3: 137 ms per loop
sage: for i in range(8): timeit('[p.to_cycles(False) for p in
Permutations(i)]')
....:
625 loops, best of 3: 22.4 µs per loop
625 loops, best of 3: 25 µs per loop
625 loops, best of 3: 49.2 µs per loop
625 loops, best of 3: 134 µs per loop
625 loops, best of 3: 542 µs per loop
125 loops, best of 3: 2.92 ms per loop
25 loops, best of 3: 18.8 ms per loop
5 loops, best of 3: 137 ms per loop
}}}
Why not having the bost of the two world devising a cut-of point ?
Once again sorry to give you more work,
Florent
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7415#comment:2>
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
-~----------~----~----~----~------~----~------~--~---
