Opened 4 years ago

Closed 4 years ago

#24434 closed enhancement (fixed)

faster reduced words

Reported by: mantepse Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords:
Cc: darij, tscrim Merged in:
Authors: Martin Rubey Reviewers: Darij Grinberg, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: bed22ef (Commits, GitHub, GitLab) Commit: bed22efa99dfbfdf508449f41d81b6633afaa7e3
Dependencies: Stopgaps:

Status badges

Description (last modified by mantepse)

Since it is usually infeasible to compute all reduced words of a permutation, an iterator may be more convenient.

As a side effect, the performance is also a bit better. Old:

sage: %timeit [len(pi.reduced_words()) for pi in Permutations(6)]
1 loop, best of 3: 42.3 s per loop
sage: version()
'SageMath version 8.2.beta1, Release Date: 2017-12-22'

New:

sage: %timeit [len(pi.reduced_words()) for pi in Permutations(6)]
1 loop, best of 3: 4.9 s per loop

Change History (9)

comment:1 Changed 4 years ago by mantepse

  • Branch set to u/mantepse/faster_reduced_words

comment:2 Changed 4 years ago by mantepse

  • Authors set to Martin Rubey
  • Cc darij tscrim added
  • Commit set to 14bfedbb03d4a82750731586d3a667376e2d8bad
  • 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 4 years ago by darij

Looks good to me (if the tests pass)!

Last edited 4 years ago by darij (previous) (diff)

comment:4 Changed 4 years ago by git

  • Commit changed from 14bfedbb03d4a82750731586d3a667376e2d8bad to 234661711ef519723bc5fe252941c0fed2e9b577

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

2346617python3 fix and fix doc

comment:5 Changed 4 years ago by mantepse

(the patchbots are failing on 8.2beta1, not on this ticket)

comment:6 Changed 4 years ago by tscrim

  • Reviewers set to Darij Grinberg, Travis Scrimshaw

One little thing:

-return [w for w in self.reduced_words_iterator()]
+return list(self.reduced_words_iterator())

Once done, you can set a positive review on my behalf.

comment:7 Changed 4 years ago by git

  • Commit changed from 234661711ef519723bc5fe252941c0fed2e9b577 to bed22efa99dfbfdf508449f41d81b6633afaa7e3

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

bed22efuse list to turn iterator into list

comment:8 Changed 4 years ago by mantepse

  • Status changed from needs_review to positive_review

Wonderful, thank you!

comment:9 Changed 4 years ago by vbraun

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