More minor tableau and skew_tableau optimizations, and moving out attacking_pairs

[darijgr]

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:

• attachment: trac_15327-qfold-dg.patch
• attachment: trac_15327-fixes-dg.patch

Depends on #15269

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

Component: combinatorics

Keywords: sage-combinat, tableau, partition, skew tableau

Author: Darij Grinberg

Reviewer: Travis Scrimshaw

Merged: sage-5.13.beta3

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

[darijgr]

Attachment: trac_15327-tableaux-improvements-dg.patch.gz

[darijgr]

comment:1

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.

[darijgr]

Description changed:

--- 
+++ 
@@ -1,3 +1 @@
 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.
-
-Patch to come in 20 minutes.

[tscrim]

comment:5

Attachment: trac_15327-review-ts.patch.gz

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

[tscrim]

Reviewer: Travis Scrimshaw

[darijgr]

Attachment: trac_15327-revrev-dg.patch.gz

[darijgr]

Description changed:

--- 
+++ 
@@ -1 +1,7 @@
 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:
+
+* [attachment: trac_15327-tableaux-improvements-dg.patch](https://github.com/sagemath/sage-prod/files/10658518/trac_15327-tableaux-improvements-dg.patch.gz)
+* [attachment: trac_15327-review-ts.patch](https://github.com/sagemath/sage-prod/files/10658519/trac_15327-review-ts.patch.gz)
+* [attachment: trac_15327-revrev-dg.patch](https://github.com/sagemath/sage-prod/files/10658520/trac_15327-revrev-dg.patch.gz)

[darijgr]

comment:7

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

[tscrim]

comment:8

two chains

XP

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

Thanks,

Travis

[darijgr]

Attachment: trac_15327-qfold-dg.patch.gz

qfold of the patches in this ticket

[darijgr]

comment:9

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

[darijgr]

Description changed:

--- 
+++ 
@@ -2,6 +2,4 @@

 Apply:

-* [attachment: trac_15327-tableaux-improvements-dg.patch](https://github.com/sagemath/sage-prod/files/10658518/trac_15327-tableaux-improvements-dg.patch.gz)
-* [attachment: trac_15327-review-ts.patch](https://github.com/sagemath/sage-prod/files/10658519/trac_15327-review-ts.patch.gz)
-* [attachment: trac_15327-revrev-dg.patch](https://github.com/sagemath/sage-prod/files/10658520/trac_15327-revrev-dg.patch.gz)
+* [attachment: trac_15327-qfold-dg.patch](https://github.com/sagemath/sage-prod/files/10658521/trac_15327-qfold-dg.patch.gz)

[darijgr]

comment:12

Attachment: trac_15327-fixes-dg.patch.gz

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

[darijgr]

Description changed:

--- 
+++ 
@@ -3,3 +3,4 @@
 Apply:

 * [attachment: trac_15327-qfold-dg.patch](https://github.com/sagemath/sage-prod/files/10658521/trac_15327-qfold-dg.patch.gz)
+* [attachment: trac_15327-fixes-dg.patch](https://github.com/sagemath/sage-prod/files/10658522/trac_15327-fixes-dg.patch.gz)

[tscrim]

comment:13

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

[darijgr]

comment:14

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

[jdemeyer]

Merged: sage-5.13.beta3