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: |
Description (last modified by )
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)
Change History (20)
Changed 9 years ago by
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
- Cc tscrim sage-combinat aschilling nthiery added
comment:3 Changed 9 years ago by
- Status changed from new to needs_review
comment:4 Changed 9 years ago by
- Description modified (diff)
Changed 9 years ago by
comment:5 Changed 9 years ago by
Hey Darij,
Here's a review patch which does:
- some docstring tweaks,
- adds a method
restriction_shape()
toskew_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
- Reviewers set to Travis Scrimshaw
Changed 9 years ago by
comment:7 Changed 9 years ago by
- 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
- 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
comment:9 Changed 9 years ago by
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
- Description modified (diff)
comment:11 Changed 9 years ago by
- Status changed from positive_review to needs_work
Changed 9 years ago by
comment:12 Changed 9 years ago by
- 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
- 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
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
- Merged in set to sage-5.13.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
Ready for review.
The
restriction_shape
method has been introduced intableau.py
because it is at least twice faster thanrestrict(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. Therestriction_outer_shape
method inskew_tableau.py
is arguably less useful (it is only about 20% faster thanrestrict(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*.