SkewTableau.rectify() optimization

[b1da87f3-e506-4c3b-95bc-e2360e109e07]

The SkewTableau.rectify() command currently runs JDT rather than taking the reading word of the tableau and Schensted-inserting it. This is inefficient for skew tableaux lambda/mu having a large inner shape mu. However, we still want to run the former algorithm if mu is small. A cutoff point between these two algorithms should be added as an input which can be optionally changed by the user.

Depends on #18024

CC: @opechenik @darijgr @MariaMonks @tscrim @sagetrac-jpswanson @sagetrac-jkeitel

Component: combinatorics

Keywords: days64, tableau, days67

Author: Maria Monks Gillespie, Oliver Pechenik

Branch/Commit: ff97f0b

Reviewer: Josh Swanson, Darij Grinberg, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/18025

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

Attachment: rectify.py.gz

[b1da87f3-e506-4c3b-95bc-e2360e109e07]

Branch: u/MariaMonks/skew_rectify

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

Changed branch from u/MariaMonks/skew_rectify to u/opechenik/skew_rectify

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

Commit: 23e2b43

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

comment:3

Seems to guess the better algorithm in most cases. Examples below. Speed-ups range from minimal to more than an order of magnitude.

sage: T = SkewTableau([[None, None, 3, 7],[1,2,4],[5,6,7]]) sage: %timeit T.rectify() 1000 loops, best of 3: 505 µs per loop sage: %timeit T.rectify(force='jdt') 1000 loops, best of 3: 501 µs per loop sage: %timeit T.rectify(force='schensted') 1000 loops, best of 3: 685 µs per loop

sage: U = SkewTableau([[None, None, None, 3,4],[None, None, 1], [None, 2], [1,5]]) sage: %timeit U.rectify() 1000 loops, best of 3: 619 µs per loop sage: %timeit U.rectify(force='jdt') 1000 loops, best of 3: 1.04 ms per loop sage: %timeit U.rectify(force='schensted') 1000 loops, best of 3: 615 µs per loop

sage: V = SkewTableau([[None for i in range(5)]]* 7 + [[None, None, None, None, 1]]) sage: %timeit V.rectify() 1000 loops, best of 3: 438 µs per loop sage: %timeit V.rectify(force='jdt') 100 loops, best of 3: 7.17 ms per loop sage: %timeit V.rectify(force='schensted') 1000 loops, best of 3: 441 µs per loop

---

New commits:

ba6d80f	skew rectification optimization!
edd9806	Merge branch 'develop' into t/18025/skew_rectify
23e2b43	Fixed bug in guessing code and slightly modified guessing algorithm to favor Schensted

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

Author: Maria Monks Gillespie, Oliver Pechenik

[633146c6-d9c3-4bcd-9486-77c47b650840]

Changed branch from u/opechenik/skew_rectify to u/jpswanson/skew_rectify

[633146c6-d9c3-4bcd-9486-77c47b650840]

Changed commit from 23e2b43 to ab4a84d

[633146c6-d9c3-4bcd-9486-77c47b650840]

comment:6

I changed 'force' to 'algorithm', which seems more common. I also cleaned up the code a bit, added error handling, and added a corresponding test. I'm not entirely convinced the output should be a StandardTableau, SemistandardTableau, or Tableau rather than just a Tableau, but I left that part as-is.

---

New commits:

ab4a84d

Renamed 'force' to 'algorithm'; cleaned up code

[633146c6-d9c3-4bcd-9486-77c47b650840]

Reviewer: Josh Swanson

[darijgr]

comment:7

Was this a review, Josh?

I have two minor gripes (although I don't have a complete review, sorry):

1. The la and la_size definitions should be inside the if algorithm is None branch. They aren't used otherwise.

2. Avoid the use of Words when you don't need them (e.g., when lists are sufficient). I am fairly sure (a quick experiment will suffice to tell) that Tableau([]).insert_word(self.to_word()) can be replaced by Tableau([]).insert_word(sum(row for row in reversed(self), [])) and will speed up the method.

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

comment:8

I implemented Darij's first suggestion, which is obviously correct.

The second suggestion doesn't work. For one thing, you are missing '[]'s. But even then your approach doesn't strip off the 'None's.

I also reordered to have it check standardness before semistandardness at the end.

Thanks for all your edits Josh!

[17b1eba5-ac2a-4aa9-b51b-fa077a4f050d]

Changed branch from u/jpswanson/skew_rectify to u/opechenik/skew_rectify

[darijgr]

comment:9

Oops, sorry. Programming in my head doesn't work as well as I wish it to. I'd still prefer to use words as little as possible. What about Tableau([]).insert_word([i for row in reversed(self) for i in row if i is not None]) ?

---

New commits:

9785351

moved definitions to where used; reordered type checking

[darijgr]

Changed commit from ab4a84d to 9785351

[633146c6-d9c3-4bcd-9486-77c47b650840]

comment:10

@darijgr: yes, I had intended that to be a review (hence the reviewers change), since I had looked through the code, checked for basic reasonability, and run the combanat doctests. I also ended up making to my mind small cleanup changes that themselves needed to be reviewed. Perhaps because I ended up making nearly as many changes as the original I shouldn't have set myself as reviewer quite yet?

As for words, I agree with darij's most recent suggestion, except it should probably be a generator rather than a list comprehension (just delete the square brackets). It seems that in practice this is what you'd want to use most of the time anyway. How does adding an iter_word or word_iter (any preference on name?) method to SkewTableau sound? It would just yield from your iterator. I'll probably add such a thing during tableaux cleanup regardless, but that's a ways off.

[darijgr]

Changed commit from 9785351 to 94af4b0

[darijgr]

Last 10 new commits:

285b0fd	rename m as n in the StandardTableau promotion methods to match the notation of the Tableau promotion methods; minor optimization
d8b310d	Some minor tweaks, removed remaining old pickles
c1c6a72	minor change, and fixing a broken iterator
f6a6540	Merge branch 'public/TransitionClonable' of trac.sagemath.org:sage into public/TransitionClonable
2c3dac1	Fixing pickling.
9e11f2d	Merge branch 'public/TransitionClonable' of git://trac.sagemath.org/sage into clone2
e9a7b56	RibbonShapedTableau instances were cuckolding from StandardRibbonShapedTableaux and thus from StandardSkewTableaux
8a21007	Travis's suggestion
c639e4f	manual merge with trac18024
94af4b0	tweak to_word methods to return non-Word results if so demanded; fix incorrect use of a^2 for a**2 (this works in the interactive session only due to the preparser); a few minor fixes here and there

[darijgr]

Changed keywords from days64, tableau to days64, tableau, days67

[darijgr]

Changed branch from u/opechenik/skew_rectify to public/ticket/18025

[darijgr]

comment:12

If my last commit (94af4b0) looks good to you, please set this to positive_review. (The other commits that were added are from #18024 and reviewed.) Thanks for this ticket!

[b1da87f3-e506-4c3b-95bc-e2360e109e07]

comment:13

Hey guys, I'm traveling this week and don't have the proper setup to look at the code, but I looked over some of the changes you guys are making and I approve! Nice work all. (This is NOT a review, just a comment.)

[tscrim]

comment:14

I don't quite like the as_word argument as you start mucking with the output type. I think the better thing to do would be to either explicitly factor out the to_word to to_flat_list and have

def to_word(self):
    return Word(self.to_flat_list())

or just call [x for row in self for x in row if x is not None] instead of self.to_word(). My personal preference is the second option since it is a one-liner with the (nested list comprehension).

[tscrim]

Dependencies: #18024

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 94af4b0 to 0b6e3f7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

4d3a52d	Merge branch 'public/ticket/18025' of git://trac.sagemath.org/sage into rekt
0b6e3f7	use list comprehension as Travis suggested

[darijgr]

comment:16

Nice suggestion about list comprehension -- it sped up the to_word on skew tableaux by a factor of 2 (even with the correct reversed(self) instead of self).

I am not sure about having two different to_word methods, though. That would require two different to_word_by_row and two different to_word_by_column methods, too, and would look a bit wasteful. Think of it as a function whose output type is a sum type parametrized by the input -- not exactly a dirty hack. On the other hand, I would really not want it called to_flat_list, since besides flattening the list it partially reverses it too.

[tscrim]

comment:17

I am okay with just not implementing the methods now and just copying the list-comprehension to the places where you just need the reading word as a list. However, I still don't like having the output type vary significantly based upon input choices. How about to_word_list? There wouldn't be much in the way of code duplication as the to_word would call to_word_list. Although I'm not completely opposed to removing the to_word altogether (but I'm not 100% sure about it either).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5ebfebc	Merge branch 'public/ticket/18025' of trac.sagemath.org:sage into public/ticket/18025
2060ebf	Removing as_word from to_word and directly constructing a list, plus doc tweaks.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0b6e3f7 to 2060ebf

[tscrim]

comment:19

I have removed the as_word argument in to_word as just using a simple list comprehension is easier and cleaner. If we find a need to not return a word and we are copying that list comprehension everywhere, then we will can add a separate method. Darij, if I understood you correctly, you were okay with allowing this and are ready to set a positive review, correct?

[tscrim]

Changed reviewer from Josh Swanson to Josh Swanson, Darij Grinberg, Travis Scrimshaw

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9a7d973

Removing some more as_word.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2060ebf to 9a7d973

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9a7d973 to 80a70ce

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

80a70ce

Fixing missing imports.

[darijgr]

comment:23

LGTM then!

[vbraun]

comment:24

docs don't build

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

ff97f0b

Getting one last reference.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 80a70ce to ff97f0b

[vbraun]

Changed branch from public/ticket/18025 to ff97f0b