#20561: Return cycle type of a permutation
-------------------------------------+-------------------------------------
Reporter: andrew.mathas | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.2
Component: group theory | Resolution:
Keywords: permutation, | Merged in:
cycle type | Reviewers:
Authors: Andrew Mathas | Work issues:
Report Upstream: N/A | Commit:
Branch: | b9acb7729e678ee46ef6db66a694c3040db830d0
u/andrew.mathas/return_cycle_type_of_a_permutation| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by tscrim):
I get much less percentage of time to construct a partition:
{{{
sage: S = SymmetricGroup(100)
sage: p = S.random_element()
sage: p
(1,60,19,34,68,36,55,29,54,89,23,87,99,95,31,24,83,98,6,82,2,10,76,5,80,52,32,77,22,37,93)(3,91,8,90,67,59,33,58,64,66,63,12,78,75,70,51,86,96,56,25,69,81,27,28,13,94,17,62,88,47,49,4,16,65,74,14,85,20,39,9,92,72,71,40,30,50,11,35,44,43)(7,84,45,73,38,21,61,97,53,18,41,79,26,100,42,48,57)(15,46)
sage: %timeit c = p.cycle_tuples()
100000 loops, best of 3: 3.63 µs per loop
sage: c = p.cycle_tuples(singletons=True)
sage: %timeit l = [len(x) for x in c]
1000000 loops, best of 3: 286 ns per loop
sage: l = [len(x) for x in c]
sage: %timeit ls = sorted(l, reverse=True)
1000000 loops, best of 3: 995 ns per loop
sage: ls = sorted(l, reverse=True)
sage: P = Partitions()
sage: %timeit p = P(ls)
100000 loops, best of 3: 8.92 µs per loop
}}}
Besides, not everything has to be ultra-super-optimized (plus these
operations are not being compared fairly since the `Partition` call is
Python). In this case, the consistency is much more desirable.
(Technically to be fair, you need to include the singletons, but I believe
these are "rare".) Averaging over all partitions and using `%lprun`, I get
that it takes ~80% of the time.
I would say what would need to be done is improve the creation time of
partitions if this is an issue for you Vincent.
Also, I don't know how it would make sense to disregard singletons. They
are needed because the cycle types (with cycle types) determine the
conjugacy classes of the symmetric group.
Side note: if you really care about speed, you should use
`list.sort(reverse=True)` because it does it in place and does not create
a second list.
--
Ticket URL: <http://trac.sagemath.org/ticket/20561#comment:11>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
