#14461 closed enhancement (fixed)
Change the method cardinality to StandardTableaux of fixed size
Reported by: | g.chatel | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.10 |
Component: | combinatorics | Keywords: | tableau, cardinality |
Cc: | sage-combinat | Merged in: | sage-5.10.beta0 |
Authors: | Grégory Châtel | Reviewers: | Travis Scrimshaw, Mike Hansen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Change the method cardinality in the class StandardTableaux_size
Before:
sage: timeit('StandardTableaux(8).cardinality()') 125 loops, best of 3: 3.53 ms per loop sage: timeit('StandardTableaux(10).cardinality()') 125 loops, best of 3: 7.58 ms per loop sage: timeit('StandardTableaux(12).cardinality()') 25 loops, best of 3: 15.5 ms per loop
With the patch:
sage: timeit('StandardTableaux(8).cardinality()') 625 loops, best of 3: 119 µs per loop sage: timeit('StandardTableaux(10).cardinality()') 625 loops, best of 3: 136 µs per loop sage: timeit('StandardTableaux(12).cardinality()') 625 loops, best of 3: 153 µs per loop sage: timeit('StandardTableaux(50).cardinality()') 625 loops, best of 3: 642 µs per loop
Apply:
Attachments (3)
Change History (18)
comment:1 Changed 10 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:4 Changed 10 years ago by
Authors: | → Grégory Chatel |
---|
Here is a new version of my patch with tests. Sorry, I'm not a native speaker and this would my first contribution.
Instead of using hook formula on every shape of Young tableau my algorithm counts the number of involution of size n which are in bijection with standard tableau of size n.
Sage seems do be limited around size 35 :
sage: timeit('StandardTableaux(35).cardinality()') 5 loops, best of 3: 5.83 s per loop
With the patch
sage: timeit('StandardTableaux(35).cardinality()') 625 loops, best of 3: 390 µs per loop
Changed 10 years ago by
Attachment: | cardinality_for_standard_tableaux-gc.patch added |
---|
comment:5 Changed 10 years ago by
Reviewers: | → Travis Scrimshaw |
---|
Hey Gregory,
This is a great speedup, and I was surprised that involutions, or at least counting them, is not currently in Sage (there must surely be a ticket for this...). Anyways, I've uploaded a review patch which adds the description of the cardinality. If you are happy with the changes, feel free to set this to positive review.
Best,
Travis
In case you are unaware, to check you should apply my review patch after yours, run sage -b
, then run sage -docbuild reference/combinat html
and look at your (local) documentation. Feel free to ask me questions if you need to.
comment:6 Changed 10 years ago by
Heh, I just added my own review patch (on top of the original, not yours). I added a reference to Fulton's Young Tableaux as well as made some minor changes. These give about a 3x speedup on the original (new) implementation. I also didn't test nearly as many values since it adds like an extra 3 seconds to the files tests.
comment:7 Changed 10 years ago by
Reviewers: | Travis Scrimshaw → Travis Scrimshaw, Mike Hansen |
---|
Hey Mike,
I'll merge your review patch with some of my doc additions and repost that (especially since you get a 3x speedup). Should be up within 15 minutes.
Changed 10 years ago by
Attachment: | trac_14461-cardinality_standard_tableaux-review-ts.patch added |
---|
comment:8 Changed 10 years ago by
Description: | modified (diff) |
---|
Hey Mike,
I've tweaked my review patch to apply after yours. If your happy with my changes, then you can set this to positive review.
Thanks,
Travis
comment:10 Changed 10 years ago by
Thanks Mike. Thanks Gregory, and welcome to the sage development community.
comment:12 Changed 10 years ago by
Status: | positive_review → needs_work |
---|
trac_14461-review-mh.patch needs a proper commit message.
Changed 10 years ago by
Attachment: | trac_14461-review-mh.patch added |
---|
comment:14 Changed 10 years ago by
Merged in: | → sage-5.10.beta0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:15 Changed 7 years ago by
Authors: | Grégory Chatel → Grégory Châtel |
---|
Hey,
Could you make the following changes:
n
than 50 of course),Thanks,
Travis