Opened 5 years ago

Closed 5 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) Commit: b87a7366fe35b3164a60f0f788ffc96d32071377
Dependencies: Stopgaps:

Description (last modified by zabrocki)

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 5 years ago by zabrocki

  • Branch set to public/zabrocki/17310/strongtableaux/transpositions
  • Commit set to a17a36a320a99d7a9f6700e8503a1d994c0f38ad

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:

a17a36afix to marked_CST_to_transposition_sequence in StrongTableaux

comment:2 follow-up: Changed 5 years ago by zabrocki

  • 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 5 years ago by tscrim

  • 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:

b87a736Changed some things around to make it faster and marked tests as long.

comment:4 in reply to: ↑ 2 Changed 5 years ago by aschilling

Hi Mike, thanks for implementing this! Looks good to me. Anne

comment:5 Changed 5 years ago by aschilling

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Anne Schilling
  • Status changed from needs_review to positive_review

comment:6 Changed 5 years ago by zabrocki

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 5 years ago by vbraun

  • Branch changed from public/combinat/strong_tableaux_transpositions-17310 to b87a7366fe35b3164a60f0f788ffc96d32071377
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.