#15655: Tweak to improve speed of generating standard tableaux
-------------------------------------+-------------------------------------
Reporter: andrew.mathas | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.1
Component: combinatorics | Resolution:
Keywords: standard tableaux | Merged in:
Authors: Andrew Mathas | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/andrew.mathas/ticket/15655 | 5e373b73a5f9223a745957a8ba144689b8fd3c93
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by andrew.mathas):
* status: new => needs_review
* commit: => 5e373b73a5f9223a745957a8ba144689b8fd3c93
Old description:
> In the iterator for generating standard tableaux the lexicographically
> last tableau is re-recomputed every time the iterator yields. Taking this
> out leads to a small speed improvements when generating moderately large
> sets of tableaux:
>
> The following table shows the timings for
> {{{
> sage: for n in range(5,15):
> ....: timeit("StandardTableaux(n)[:];",number=6)
> }}}
> before and after the patch:
>
> ||= **n** ||= **Before** =||= **After** =||
> || 5|| 6.2ms|| 5.4ms||
> || 6|| 14.0ms|| 12.4ms||
> || 7|| 43.3ms|| 40.5ms||
> || 8|| 151ms|| 140ms||
> || 9|| 558ms|| 509ms||
> ||10|| 2.14s|| 1.97s||
> ||11|| 8.56s|| 7.82s||
> ||12|| 35.4s|| 34.55s||
> ||13|| 161.57s||145.11s||
> ||14|| 711.13s||633.93s||
>
> These timings were done on my laptop, a macbook pro running sage 6.0.
> (Actually, the last two sets were done with just one iteration:)
New description:
In the iterator for generating standard tableaux the lexicographically
last tableau is re-recomputed every time the iterator yields. Taking this
out leads to a small speed improvements when generating moderately large
sets of tableaux:
The following table shows the timings for
{{{
sage: for n in range(5,15):
....: timeit("StandardTableaux(n)[:];",number=6)
}}}
before and after the patch:
||= **n** ||= **Before** =||= **After** =||
|| 5|| 6.2ms|| 5.4ms||
|| 6|| 14.0ms|| 12.4ms||
|| 7|| 43.3ms|| 40.5ms||
|| 8|| 151ms|| 140ms||
|| 9|| 558ms|| 509ms||
||10|| 2.14s|| 1.97s||
||11|| 8.56s|| 7.82s||
||12|| 35.4s|| 34.55s||
||13|| 161.57s||145.11s||
||14|| 711.13s||633.93s||
These timings were done on my laptop, a macbook pro running sage 6.0.
(Actually, the last two sets were done with just one timing:)
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=5e373b73a5f9223a745957a8ba144689b8fd3c93
5e373b7]||{{{Minor tweak to tableau.py}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/15655#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 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/groups/opt_out.
