Opened 6 years ago
Closed 6 years ago
#17310 closed enhancement (fixed)
improvement to StrongTableaux to_transposition algorithm
Reported by: | zabrocki | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.4 |
Component: | combinatorics | Keywords: | tableaux |
Cc: | aschilling, tscrim | Merged in: | |
Authors: | Mike Zabrocki | Reviewers: | Travis Scrimshaw, Anne Schilling |
Report Upstream: | N/A | Work issues: | |
Branch: | b87a736 (Commits, GitHub, GitLab) | Commit: | b87a7366fe35b3164a60f0f788ffc96d32071377 |
Dependencies: | Stopgaps: |
Description (last modified by )
In discussions after #17252, Jennifer Morse pointed out that the algorithm to convert a strong marked column strict tableau to a sequence of transpositions could be made more efficient by always choosing the largest rightmost marking as the end point. The previous version of this algorithm scanned the potential marked column strict tableaux from right to left and pulled off markings if applying a transposition lowered the length of the core by one. This version will test fewer potential marked ribbons.
Change History (7)
comment:1 Changed 6 years ago by
- Branch set to public/zabrocki/17310/strongtableaux/transpositions
- Commit set to a17a36a320a99d7a9f6700e8503a1d994c0f38ad
comment:2 follow-up: ↓ 4 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
- Type changed from PLEASE CHANGE to enhancement
This version seems to be slightly faster in practice. On my laptop I see around 24-25 seconds with the patch, 24-26 without.
comment:3 Changed 6 years ago by
- Branch changed from public/zabrocki/17310/strongtableaux/transpositions to public/combinat/strong_tableaux_transpositions-17310
- Commit changed from a17a36a320a99d7a9f6700e8503a1d994c0f38ad to b87a7366fe35b3164a60f0f788ffc96d32071377
- Reviewers set to Travis Scrimshaw
So I've made some changes and massaged out some more speed. My timings are below. I've also marked two tests as long because the file takes some 110s to run on mine (each were about 9s). However I'll let someone else (Anne) do the final review on the math portion.
Original timings:
sage: CST_to_trans = StrongTableaux.marked_CST_to_transposition_sequence sage: %timeit CST_to_trans([[-1, -1, -1], [1]], 2) 100 loops, best of 3: 8.32 ms per loop sage: %timeit CST_to_trans([[-1, -2, -2, -2, -2], [-2, 2], [2]], 3) 10 loops, best of 3: 21.1 ms per loop sage: %timeit CST_to_trans([[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5], [5]],3) 10 loops, best of 3: 104 ms per loop sage: %timeit CST_to_trans([[-1, -2, -3, 4, -7], [-4, -6], [-5, 6]],3) 10 loops, best of 3: 29.7 ms per loop sage: %timeit CST_to_trans([], 2) 100000 loops, best of 3: 2.46 µs per loop
Without my changes:
sage: CST_to_trans = StrongTableaux.marked_CST_to_transposition_sequence sage: %timeit CST_to_trans([[-1, -1, -1], [1]], 2) 100 loops, best of 3: 8.29 ms per loop sage: %timeit CST_to_trans([[-1, -2, -2, -2, -2], [-2, 2], [2]], 3) 10 loops, best of 3: 21 ms per loop sage: %timeit CST_to_trans([[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5], [5]],3) 10 loops, best of 3: 48 ms per loop sage: %timeit CST_to_trans([[-1, -2, -3, 4, -7], [-4, -6], [-5, 6]],3) 10 loops, best of 3: 29.3 ms per loop sage: %timeit CST_to_trans([], 2) 100000 loops, best of 3: 2.4 µs per loop
With my changes:
sage: CST_to_trans = StrongTableaux.marked_CST_to_transposition_sequence sage: %timeit CST_to_trans([[-1, -1, -1], [1]], 2) 100 loops, best of 3: 7.7 ms per loop sage: %timeit CST_to_trans([[-1, -2, -2, -2, -2], [-2, 2], [2]], 3) 10 loops, best of 3: 18.3 ms per loop sage: %timeit CST_to_trans([[-1, -2, -5, 5, -5, 5, -5], [-3, -4, 5, 5], [5]],3) 10 loops, best of 3: 43.3 ms per loop sage: %timeit CST_to_trans([[-1, -2, -3, 4, -7], [-4, -6], [-5, 6]],3) 10 loops, best of 3: 26.1 ms per loop sage: %timeit CST_to_trans([], 2) 100000 loops, best of 3: 2 µs per loop
New commits:
b87a736 | Changed some things around to make it faster and marked tests as long.
|
comment:4 in reply to: ↑ 2 Changed 6 years ago by
Hi Mike, thanks for implementing this! Looks good to me. Anne
comment:5 Changed 6 years ago by
- Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Anne Schilling
- Status changed from needs_review to positive_review
comment:6 Changed 6 years ago by
I've been calculating larger examples to make sure going from and to transposition sequences are consistent and have found no faults.
Thanks Travis and Anne.
comment:7 Changed 6 years ago by
- Branch changed from public/combinat/strong_tableaux_transpositions-17310 to b87a7366fe35b3164a60f0f788ffc96d32071377
- Resolution set to fixed
- Status changed from positive_review to closed
I will continue to run a few tests to make sure, but I think that this version shaves a few seconds off of the tests of k_tableau.py
New commits:
fix to marked_CST_to_transposition_sequence in StrongTableaux