#7415: cycle decomposition and random element are now much faster.
------------------------------+---------------------------------------------
Reporter: ylchapuy | Owner: mhansen
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.2.1
Component: combinatorics | Keywords: permutation
Work_issues: | Author: Yann Laigle-Chapuy, Florent Hivert
Reviewer: Florent Hivert | Merged:
------------------------------+---------------------------------------------
Changes (by newvalueoldvalue):
* status: needs_work => needs_review
* work_issues: Speed regression for small input =>
* milestone: sage-combinat => sage-4.2.1
* author: Yann Laigle-Chapuy => Yann Laigle-Chapuy, Florent Hivert
Comment:
Hi Yann,
I just uploaded a new patch which contains four different methods:
- {{{to_cycles }}} : use a binary vector
- {{{_to_cycles_orig}}} : the original implementation
- {{{_to_cycles_set }}} : the modification of your implementation using a
sage set
- {{{_to_cycles_list}}} : your implementation
I left in the code a little command to benchmark these four functions:
On small permutations the results are:
{{{
sage: for size in range(9): # not tested
print size
lp = Permutations(size).list()
timeit('[p.to_cycles(False) for p in lp]')
timeit('[p._to_cycles_set(False) for p in lp]')
timeit('[p._to_cycles_list(False) for p in lp]')
timeit('[p._to_cycles_orig(False) for p in lp]')
0
625 loops, best of 3: 4.6 µs per loop
625 loops, best of 3: 16.8 µs per loop
625 loops, best of 3: 7.59 µs per loop
625 loops, best of 3: 2.97 µs per loop
1
625 loops, best of 3: 4.18 µs per loop
625 loops, best of 3: 9.06 µs per loop
625 loops, best of 3: 7.6 µs per loop
625 loops, best of 3: 4.78 µs per loop
2
625 loops, best of 3: 11.3 µs per loop
625 loops, best of 3: 22.1 µs per loop
625 loops, best of 3: 20.2 µs per loop
625 loops, best of 3: 12.9 µs per loop
3
625 loops, best of 3: 42 µs per loop
625 loops, best of 3: 73.3 µs per loop
625 loops, best of 3: 72.7 µs per loop
625 loops, best of 3: 47.7 µs per loop
4
625 loops, best of 3: 192 µs per loop
625 loops, best of 3: 325 µs per loop
625 loops, best of 3: 333 µs per loop
625 loops, best of 3: 224 µs per loop
5
625 loops, best of 3: 1.08 ms per loop
125 loops, best of 3: 1.75 ms per loop
125 loops, best of 3: 1.87 ms per loop
625 loops, best of 3: 1.33 ms per loop
6
125 loops, best of 3: 7.34 ms per loop
25 loops, best of 3: 11.8 ms per loop
25 loops, best of 3: 12.8 ms per loop
25 loops, best of 3: 9.28 ms per loop
7
5 loops, best of 3: 58.5 ms per loop
5 loops, best of 3: 91.1 ms per loop
5 loops, best of 3: 99.1 ms per loop
5 loops, best of 3: 72.7 ms per loop
8
5 loops, best of 3: 501 ms per loop
5 loops, best of 3: 772 ms per loop
5 loops, best of 3: 866 ms per loop
5 loops, best of 3: 631 ms per loop
}}}
On bigger permutations (I don't test the original implantation which is
very slow:
{{{
for size in [10, 20, 50, 75, 100, 200, 500, 1000, # not tested
2000, 5000, 10000, 15000, 20000, 30000,
50000, 80000, 100000]:
print(size)
lp = [Permutations(size).random_element() for i in range(20)]
timeit("[p.to_cycles() for p in lp]")
timeit("[p._to_cycles_set() for p in lp]")
timeit("[p._to_cycles_list() for p in lp]") # not tested
10
625 loops, best of 3: 276 µs per loop
625 loops, best of 3: 367 µs per loop
625 loops, best of 3: 442 µs per loop
20
625 loops, best of 3: 428 µs per loop
625 loops, best of 3: 492 µs per loop
625 loops, best of 3: 687 µs per loop
50
625 loops, best of 3: 872 µs per loop
625 loops, best of 3: 905 µs per loop
625 loops, best of 3: 1.45 ms per loop
75
625 loops, best of 3: 1.21 ms per loop
625 loops, best of 3: 1.19 ms per loop
125 loops, best of 3: 2.08 ms per loop
100
125 loops, best of 3: 1.53 ms per loop
625 loops, best of 3: 1.5 ms per loop
125 loops, best of 3: 2.68 ms per loop
200
125 loops, best of 3: 2.94 ms per loop
125 loops, best of 3: 2.66 ms per loop
125 loops, best of 3: 5.31 ms per loop
500
125 loops, best of 3: 7.5 ms per loop
125 loops, best of 3: 7.2 ms per loop
25 loops, best of 3: 14.7 ms per loop
1000
25 loops, best of 3: 14.8 ms per loop
25 loops, best of 3: 13.9 ms per loop
25 loops, best of 3: 31.3 ms per loop
2000
25 loops, best of 3: 29.1 ms per loop
25 loops, best of 3: 28.1 ms per loop
5 loops, best of 3: 72.8 ms per loop
5000
5 loops, best of 3: 74 ms per loop
5 loops, best of 3: 69.1 ms per loop
5 loops, best of 3: 252 ms per loop
10000
5 loops, best of 3: 146 ms per loop
5 loops, best of 3: 151 ms per loop
5 loops, best of 3: 833 ms per loop
15000
5 loops, best of 3: 229 ms per loop
5 loops, best of 3: 236 ms per loop
5 loops, best of 3: 1.71 s per loop
20000
5 loops, best of 3: 317 ms per loop
5 loops, best of 3: 331 ms per loop
5 loops, best of 3: 2.85 s per loop
30000
5 loops, best of 3: 472 ms per loop
5 loops, best of 3: 553 ms per loop
5 loops, best of 3: 6.01 s per loop
50000
5 loops, best of 3: 844 ms per loop
5 loops, best of 3: 1.02 s per loop
5 loops, best of 3: 15.9 s per loop
80000
5 loops, best of 3: 1.45 s per loop
5 loops, best of 3: 1.81 s per loop
> 2 min...
100000
5 loops, best of 3: 1.87 s per loop
5 loops, best of 3: 2.43 s per loop
> 2 min ...
}}}
Since the default implementation is only beated by less that 10% I haven't
written any algorithm selection. I kept the other implementation because
there are some plan to optimize the datastructure for permutations so that
those timings can change.
I also took the chance to completely rewrite random_element which was
incredibly slow.
Considering your function as positively reviewed by me, can you please
review mine ?
Cheers,
Florent
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7415#comment:4>
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
-~----------~----~----~----~------~----~------~--~---
