Speeding up tableau's cells_containing and weight methods

[darijgr]

I know that the current implementation of tableaux in Sage is not long for this world (mutability WTF), but here are two small pieces of simple code that can be improved:
Before:

sage: %timeit Tableau([[1,1,2,8,9],[2,5,6,11],[3,7,7,13],[4,8,9],[5],[13],[14]]).cells_containing(4)
1000 loops, best of 3: 449 us per loop

After:

sage: %timeit Tableau([[1,1,2,8,9],[2,5,6,11],[3,7,7,13],[4,8,9],[5],[13],[14]]).cells_containing(4)
10000 loops, best of 3: 81.5 us per loop

Before:

sage: %timeit Tableau([[1,1,2,8,9],[2,5,6,11],[3,7,7,13],[4,8,9],[5],[13],[14]]).weight()
10000 loops, best of 3: 190 us per loop

After:

sage: %timeit Tableau([[1,1,2,8,9],[2,5,6,11],[3,7,7,13],[4,8,9],[5],[13],[14]]).weight2()
10000 loops, best of 3: 87.4 us per loop

Apply:

• attachment: trac_15269-tableau-speedup-dg.patch​
• attachment: trac_15269-review-ts.patch​

CC: @tscrim @sagetrac-sage-combinat @anneschilling

Component: combinatorics

Keywords: tableau, combinat

Author: Darij Grinberg

Reviewer: Travis Scrimshaw

Merged: sage-5.13.beta1

Issue created by migration from https://trac.sagemath.org/ticket/15269

[darijgr]

Attachment: trac_15269-tableau-speedup-dg.patch.gz

[tscrim]

comment:2

Attachment: trac_15269-review-ts.patch.gz

Hey Darij,

Here's a small review patch which checks the old implementation agrees with the new one and some micro-optimizations where I was able to squeeze out a little bit more speed (on the order of 1%, but it's there). If you're happy with my changes, then go ahead and set a positive review.

Best,

Travis

[tscrim]

Reviewer: Travis Scrimshaw

[darijgr]

comment:3

Thanks for the review! Yeah, nice fixes. I didn't know one could write max(spam for x in eggs) and get a maximum of the iterator.

for the patchbot:

apply trac_15269-tableau-speedup-dg.patch​ trac_15269-review-ts.patch​

[jdemeyer]

Merged: sage-5.13.beta1