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:  sage6.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)  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 followup: ↓ 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 2425 seconds with the patch, 2426 without.
comment:3 Changed 6 years ago by
 Branch changed from public/zabrocki/17310/strongtableaux/transpositions to public/combinat/strong_tableaux_transpositions17310
 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_transpositions17310 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