#7408: Improve the speed of RSK
-----------------------------+----------------------------------------------
Reporter: mhansen | Owner: mhansen
Type: defect | Status: needs_review
Priority: major | Milestone: sage-combinat
Component: combinatorics | Keywords:
Work_issues: | Author: Mike Hansen
Reviewer: | Merged:
-----------------------------+----------------------------------------------
Comment(by ylchapuy):
A last slight improvement would be to avoid the burden of keeping maxes
and lenths.
A row version would then be:
{{{
def robinson_schensted(self):
from bisect import bisect
p = [] #the "left" tableau
q = [] #the "recording" tableau
#For each x in self, insert x into the tableau p.
for i,x in enumerate(self):
row_counter = 0
for r in p:
if r[-1] > x:
y_pos = bisect(r, x)
x, r[y_pos] = r[y_pos], x
row_counter += 1
else:
break
if row_counter == len(p):
p.append([x])
q.append([i+1])
else:
r.append(x)
q[row_counter].append(i+1)
return [tableau.Tableau(p),tableau.Tableau(q)]
}}}
This gives me something like a 15% speedup.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7408#comment:3>
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
-~----------~----~----~----~------~----~------~--~---
