Opened 2 years ago
Closed 2 years ago
#23862 closed enhancement (fixed)
speed_up_left_and_right_key
Reported by:  mantepse  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  combinatorics  Keywords:  
Cc:  Merged in:  
Authors:  Martin Rubey  Reviewers:  Travis Scrimshaw, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  d4931f0 (Commits)  Commit:  d4931f0ec98fbe21b6edf6ee672013df42221f3e 
Dependencies:  Stopgaps: 
Description (last modified by )
old:
sage: l = [t for t in SemistandardTableaux(7)] sage: %timeit [t.left_key_tableau() for t in l] 1 loop, best of 3: 7.8 s per loop sage: %timeit [t.is_key_tableau() for t in l] 1 loop, best of 3: 4.33 s per loop
The remaining time of left_key_tableau
is spent in computing the conjugate of a partition, which will be optimized in a separate ticket.
new:
sage: %timeit [t.left_key_tableau2() for t in l] 1 loop, best of 3: 3.61 s per loop sage: %timeit [t.is_key_tableau2() for t in l] 1 loop, best of 3: 1.51 s per loop
Achieved by removing a test which checked whether the input is a key tableau, probably intended to save work.
Change History (10)
comment:1 Changed 2 years ago by
 Branch set to u/mantepse/speed_up_left_and_right_key
comment:2 Changed 2 years ago by
 Commit set to c859cf2e15dd2c3a1d2840462f352b11e1c3dbea
 Component changed from PLEASE CHANGE to combinatorics
 Description modified (diff)
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to enhancement
comment:3 Changed 2 years ago by
comment:4 Changed 2 years ago by
Thanks for looking! One quick thing: I thought about using sets, but apparently I cannot assume that the elements of the tableau are hashable.
I am guessing though that the method doesn't make sense then...
comment:5 Changed 2 years ago by
Indeed... I thought your entries would always be integers. I am not a tableau specialist at all and I just looked at your example from the ticket description where the rows are even nondecreasing. You can still either
 try with sets inside a
try/except
and relies on the other version for nonhashable ones  have a boolean flag somewhere
hashable
orinteger_entries
orincreasing
or ... (default toFalse
) that would switch to more efficient versions
Perhaps it is too much bikeshedding...
comment:6 Changed 2 years ago by
Since is_key_tableau
is (after this patch) unused in sage, I'd rather leave it at that and spend my energy elsewhere (in particular, in Tableau.conjugate
)
comment:7 Changed 2 years ago by
Also, it is faster to use just one all
check, which does shortcircuit as soon as it gets a False
with generators:
return all(x in T_conj[i1] for i in range(1, len(T_conj)) for x in T_conj[i])
The definition allows general elements; however, I think it is a fair assumption that all entries of the tableau are hashable.
comment:8 Changed 2 years ago by
 Commit changed from c859cf2e15dd2c3a1d2840462f352b11e1c3dbea to d4931f0ec98fbe21b6edf6ee672013df42221f3e
Branch pushed to git repo; I updated commit sha1. New commits:
d4931f0  move loop into all check, thanks Travis!

comment:9 Changed 2 years ago by
 Reviewers set to Travis Scrimshaw, Frédéric Chapoton
 Status changed from needs_review to positive_review
ok
comment:10 Changed 2 years ago by
 Branch changed from u/mantepse/speed_up_left_and_right_key to d4931f0ec98fbe21b6edf6ee672013df42221f3e
 Resolution set to fixed
 Status changed from positive_review to closed
Some possible improvements:
set.issubset
as in Doing loops is always a bad idea in Python. If you need speed, avoid them as much as possible.