#7414: improve {from,to}_inversion_vector
--------------------------------------------------------+-------------------
Reporter: ylchapuy | Owner: mhansen
Type: defect | Status:
needs_work
Priority: major | Milestone:
sage-combinat
Component: combinatorics | Keywords:
permutations, inversion vector, lehmer code
Work_issues: Large speed regression for small entries | Author: Yann
Laigle-Chapuy
Reviewer: Florent Hivert | Merged:
--------------------------------------------------------+-------------------
Changes (by hivert):
* keywords: => permutations, inversion vector, lehmer code
* reviewer: => Florent Hivert
* status: needs_review => needs_work
* work_issues: => Large speed regression for small entries
Comment:
Yes, this is very good for large permutaions ! but is is much slower on
small permutations, where I will use it :-) Sorry for this...
Before:
{{{
625 loops, best of 3: 16.4 µs per loop
625 loops, best of 3: 19.2 µs per loop
625 loops, best of 3: 33.3 µs per loop
625 loops, best of 3: 87.4 µs per loop
625 loops, best of 3: 356 µs per loop
125 loops, best of 3: 2.04 ms per loop
25 loops, best of 3: 14.2 ms per loop
5 loops, best of 3: 117 ms per loop
}}}
after:
{{{
625 loops, best of 3: 18.1 µs per loop
625 loops, best of 3: 19.9 µs per loop
625 loops, best of 3: 51.2 µs per loop
625 loops, best of 3: 166 µs per loop
625 loops, best of 3: 794 µs per loop
125 loops, best of 3: 4.86 ms per loop
25 loops, best of 3: 33.2 ms per loop
5 loops, best of 3: 271 ms per loop
}}}
I suggest you to reinstate the former implementation and to change from
one to the other depending on the size of the permutations. I wrote the
same in MuPAD, the cut-of point where around 18.
Moreover, since the Lehmer code is the inversion vector of the inverse,
you can speed up it for large n. Also, if you would take the chance to
write the definition of the lehmer code (c_i = the number of j > i s.t.
s(j) < s(i)) and to put a link beetween those two methods, then I would be
extremely happy to put a positive review.
Sorry to give you more work.
Cheers,
Florent
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7414#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
-~----------~----~----~----~------~----~------~--~---
