#17310: improvement to StrongTableaux to_transposition algorithm
-------------------------------------+-------------------------------------
Reporter: zabrocki | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: tableaux | Merged in:
Authors: Mike Zabrocki | Reviewers: Travis Scrimshaw
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/strong_tableaux_transpositions-17310|
b87a7366fe35b3164a60f0f788ffc96d32071377
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by tscrim):
* commit: a17a36a320a99d7a9f6700e8503a1d994c0f38ad =>
b87a7366fe35b3164a60f0f788ffc96d32071377
* branch: public/zabrocki/17310/strongtableaux/transpositions =>
public/combinat/strong_tableaux_transpositions-17310
* reviewer: => Travis Scrimshaw
Comment:
So I've made some changes and massaged out some more speed. My timings are
below. I've also marked two tests as long because the file takes some 110s
to run on mine (each were about 9s). However I'll let someone else (Anne)
do the final review on the math portion.
----
Original timings:
{{{
sage: CST_to_trans = StrongTableaux.marked_CST_to_transposition_sequence
sage: %timeit CST_to_trans([[-1, -1, -1], [1]], 2)
100 loops, best of 3: 8.32 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -2, -2, -2], [-2, 2], [2]], 3)
10 loops, best of 3: 21.1 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5],
[5]],3)
10 loops, best of 3: 104 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -3, 4, -7], [-4, -6], [-5, 6]],3)
10 loops, best of 3: 29.7 ms per loop
sage: %timeit CST_to_trans([], 2)
100000 loops, best of 3: 2.46 µs per loop
}}}
Without my changes:
{{{
sage: CST_to_trans = StrongTableaux.marked_CST_to_transposition_sequence
sage: %timeit CST_to_trans([[-1, -1, -1], [1]], 2)
100 loops, best of 3: 8.29 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -2, -2, -2], [-2, 2], [2]], 3)
10 loops, best of 3: 21 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5],
[5]],3)
10 loops, best of 3: 48 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -3, 4, -7], [-4, -6], [-5, 6]],3)
10 loops, best of 3: 29.3 ms per loop
sage: %timeit CST_to_trans([], 2)
100000 loops, best of 3: 2.4 µs per loop
}}}
With my changes:
{{{
sage: CST_to_trans = StrongTableaux.marked_CST_to_transposition_sequence
sage: %timeit CST_to_trans([[-1, -1, -1], [1]], 2)
100 loops, best of 3: 7.7 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -2, -2, -2], [-2, 2], [2]], 3)
10 loops, best of 3: 18.3 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5],
[5]],3)
10 loops, best of 3: 43.3 ms per loop
sage: %timeit CST_to_trans([[-1, -2, -3, 4, -7], [-4, -6], [-5, 6]],3)
10 loops, best of 3: 26.1 ms per loop
sage: %timeit CST_to_trans([], 2)
100000 loops, best of 3: 2 µs per loop
}}}
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=b87a7366fe35b3164a60f0f788ffc96d32071377
b87a736]||{{{Changed some things around to make it faster and marked tests
as long.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17310#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 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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
