Opened 8 years ago

Closed 8 years ago

#15269 closed enhancement (fixed)

Speeding up tableau's cells_containing and weight methods

Reported by: darij Owned by:
Priority: minor Milestone: sage-5.13
Component: combinatorics Keywords: tableau, combinat
Cc: tscrim, sage-combinat, aschilling Merged in: sage-5.13.beta1
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

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:

Attachments (2)

trac_15269-tableau-speedup-dg.patch (3.6 KB) - added by darij 8 years ago.
trac_15269-review-ts.patch (1.9 KB) - added by tscrim 8 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 8 years ago by darij

  • Status changed from new to needs_review

Changed 8 years ago by darij

Changed 8 years ago by tscrim

comment:2 Changed 8 years ago by tscrim

  • Description modified (diff)
  • Reviewers set to Travis Scrimshaw

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

comment:3 Changed 8 years ago by darij

  • Status changed from needs_review to positive_review

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​

comment:4 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.13.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.