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: sage-8.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 mantepse)

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 mantepse

  • Branch set to u/mantepse/speed_up_left_and_right_key

comment:2 Changed 2 years ago by mantepse

  • Authors set to Martin Rubey
  • 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 vdelecroix

Some possible improvements:

  • if your tableau has only one row you just have to test whether the first and last elements coincide (ie no need to take the time consuming conjugate)
  • similarly, if your tableaux has one column there is nothing to check
  • now for the remaining cases, you would better use set.issubset as in
    s = set(T_conj[0])
    for i in range(1, len(T_conj)):
        ss = set(T_conj[i])
        if not ss.issubset(s):
            return False
        s = ss
    
    Doing loops is always a bad idea in Python. If you need speed, avoid them as much as possible.

comment:4 Changed 2 years ago by mantepse

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 vdelecroix

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 non-decreasing. You can still either

  • try with sets inside a try/except and relies on the other version for non-hashable ones
  • have a boolean flag somewhere hashable or integer_entries or increasing or ... (default to False) that would switch to more efficient versions

Perhaps it is too much bikeshedding...

comment:6 Changed 2 years ago by mantepse

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 tscrim

Also, it is faster to use just one all check, which does short-circuit as soon as it gets a False with generators:

return all(x in T_conj[i-1] 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 git

  • Commit changed from c859cf2e15dd2c3a1d2840462f352b11e1c3dbea to d4931f0ec98fbe21b6edf6ee672013df42221f3e

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

d4931f0move loop into all check, thanks Travis!

comment:9 Changed 2 years ago by chapoton

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

  • Branch changed from u/mantepse/speed_up_left_and_right_key to d4931f0ec98fbe21b6edf6ee672013df42221f3e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.