#7408: Improve the speed of RSK
------------------------------+---------------------------------------------
Reporter: mhansen | Owner: mhansen
Type: defect | Status: needs_review
Priority: major | Milestone: sage-combinat
Component: combinatorics | Keywords: Robinson-Schensted
Work_issues: | Author: Mike Hansen
Reviewer: Florent Hivert | Merged:
------------------------------+---------------------------------------------
Changes (by hivert):
* keywords: => Robinson-Schensted
* reviewer: => Florent Hivert
Comment:
This patch greatly improve the speed of RSK even for small permutations:
{{{
sage: p4 = Permutations(4).list()
sage: timeit("map(attrcall('robinson_schensted'), p4)")
625 loops, best of 3: 1.22 ms per loop
sage: p = Permutations(1000).random_element()
sage: timeit("p.robinson_schensted()")
25 loops, best of 3: 19.5 ms per loop
}}}
whereas we had:
{{{
sage: timeit("map(attrcall('robinson_schensted'), p4)")
625 loops, best of 3: 1.34 ms per loop
sage: p = Permutations(1000).random_element()
sage: timeit("p.robinson_schensted()")
5 loops, best of 3: 265 ms per loop
}}}
However, I was not sure that bisect cut the thing correctly in case of
repeated letters so I had to write another test. I'd rather see it
integrated into sage.
Please review this minor change.
Otherwise you can put a postive review.
Cheers,
Florent
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7408#comment:5>
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
-~----------~----~----~----~------~----~------~--~---
