Opened 9 years ago

Closed 9 years ago

#15327 closed enhancement (fixed)

More minor tableau and skew_tableau optimizations, and moving out attacking_pairs

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

Status badges

Description (last modified by darij)

This patch brings some little speedups on tableaux and skew tableaux, in particular copying over the #15269 fixes to skew_tableau.py. It also modifies the semantics of the to_chain function so as to allow an optional max_entry parameter (which makes it return a chain of a given length -- useful if one is considering semistandard tableaux with ceiling higher than the highest entry). Furthermore it moves the attacking_pairs method from tableau.py to partition.py, and deprecates it in tableau.py. In the only place where this method is used, it is factored in for speed reasons.

Apply:

Attachments (5)

trac_15327-tableaux-improvements-dg.patch (30.3 KB) - added by darij 9 years ago.
trac_15327-review-ts.patch (10.5 KB) - added by tscrim 9 years ago.
trac_15327-revrev-dg.patch (1.3 KB) - added by darij 9 years ago.
trac_15327-qfold-dg.patch (32.1 KB) - added by darij 9 years ago.
qfold of the patches in this ticket
trac_15327-fixes-dg.patch (13.7 KB) - added by darij 9 years ago.

Download all attachments as: .zip

Change History (20)

Changed 9 years ago by darij

comment:1 Changed 9 years ago by darij

Ready for review.

The restriction_shape method has been introduced in tableau.py because it is at least twice faster than restrict(i).shape() (probably due to the hackery with exceptions in the latter) and the shape of the restriction seems to be used more often than the restriction itself. The restriction_outer_shape method in skew_tableau.py is arguably less useful (it is only about 20% faster than restrict(i).outer_shape() in the cases I checked) and I will remove it if you think it clutters up stuff.

Some of the doc bugs fixed here are due to me *oops*.

comment:2 Changed 9 years ago by darij

  • Cc tscrim sage-combinat aschilling nthiery added

comment:3 Changed 9 years ago by darij

  • Status changed from new to needs_review

comment:4 Changed 9 years ago by darij

  • Description modified (diff)

Changed 9 years ago by tscrim

comment:5 Changed 9 years ago by tscrim

Hey Darij,

Here's a review patch which does:

  • some docstring tweaks,
  • adds a method restriction_shape() to skew_tableau.py (which how it's done is [much] faster than the direct implementation I tried),
  • and does some minor speedup to the creation of SkewPartition.

Before:

sage: %timeit skp = SkewPartition([[3,2,1],[2,1]])
10000 loops, best of 3: 184 us per loop
sage: %timeit skp = SkewPartition([[3,2,1],[2,1]])
1000 loops, best of 3: 178 us per loop

With patch:

sage: %timeit skp = SkewPartition([[3,2,1],[2,1]])
10000 loops, best of 3: 115 us per loop
sage: %timeit skp = SkewPartition([[3,2,1],[2,1]])
1000 loops, best of 3: 112 us per loop

If you're happy with my changes, then you can go ahead and set this to positive review.

Best,
Travis

comment:6 Changed 9 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Changed 9 years ago by darij

comment:7 Changed 9 years ago by darij

  • Description modified (diff)

Thanks a lot!! Pro forma, I'll let you set the positive_review mark since I added two chains...

for the patchbot:

apply trac_15327-tableaux-improvements-dg.patch​ trac_15327-review-ts.patch trac_15327-revrev-dg.patch

comment:8 Changed 9 years ago by tscrim

  • Status changed from needs_review to positive_review

two chains

XP

Positive review then. Could you fold the 3 patches together and re-upload?

Thanks,
Travis

Changed 9 years ago by darij

qfold of the patches in this ticket

comment:9 Changed 9 years ago by darij

Thank you again -- done. And yes, my ability to make typos while fixing them is uncontested.

for the patchbot:

apply trac_15327-qfold-dg.patch

comment:10 Changed 9 years ago by darij

  • Description modified (diff)

comment:11 Changed 9 years ago by darij

  • Status changed from positive_review to needs_work

Changed 9 years ago by darij

comment:12 Changed 9 years ago by darij

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I wish it had been just typos. There were two major oopses in my version of the inversions method. Should be fixed now (speed improvement is still there). Now it probably needs review again, but at least that should be easy...

for the patchbot:

apply trac_15327-qfold-dg.patch trac_15327-fixes-dg.patch

comment:13 Changed 9 years ago by tscrim

  • Status changed from needs_review to positive_review

I feel bad for not catching the errors on the first go-around. Back to positive review.

comment:14 Changed 9 years ago by darij

Thanks a lot for your patience, and no problem -- I should feel worse for making them in the first place!

comment:15 Changed 9 years ago by jdemeyer

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