Opened 8 years ago

Last modified 8 years ago

#15269 closed enhancement

Speeding up tableau's cells_containing and weight methods — at Version 2

Reported by: darij Owned by:
Priority: minor Milestone: sage-5.13
Component: combinatorics Keywords: tableau, combinat
Cc: tscrim, sage-combinat, aschilling Merged in:
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:

Change History (4)

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

Note: See TracTickets for help on using tickets.