Opened 7 years ago
Closed 7 years ago
#6631 closed defect (fixed)
[with patch, positive review] speed up is_lyndon method for words
Reported by: | saliola | Owned by: | Franco Saliola |
---|---|---|---|
Priority: | major | Milestone: | sage-4.1.2 |
Component: | combinatorics | Keywords: | words |
Cc: | slabbe | Merged in: | Sage 4.1.2.alpha0 |
Authors: | Franco Saliola | Reviewers: | Vincent Delecroix, Minh Van Nguyen |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The current implementation of the method is_lyndon is too slow
sage: c = words.ChristoffelWord(380447,34369) sage: c Lower Christoffel word of slope 380447/34369 over Ordered Alphabet [0, 1] sage: c.length() 414816 sage: time c.is_lyndon() CPU times: user 84.15 s, sys: 0.17 s, total: 84.33 s Wall time: 84.52 s True
Attachments (3)
Change History (11)
Changed 7 years ago by saliola
comment:1 Changed 7 years ago by saliola
Don't apply trac_6631-is_lyndon.2.patch, it is a copy of the other, and should be deleted.
comment:2 Changed 7 years ago by saliola
- Summary changed from speed up is_lyndon method for words to [with patch; needs review] speed up is_lyndon method for words
Here is the new timing:
sage: c = words.ChristoffelWord(380447,34369) sage: time c.is_lyndon() CPU times: user 1.15 s, sys: 0.00 s, total: 1.15 s Wall time: 1.15 s True
That's much better.
comment:3 Changed 7 years ago by vdelecroix
- Reviewers set to vdelecroix
comment:4 follow-up: ↓ 5 Changed 7 years ago by vdelecroix
The end of the loop can be simplified (there is no break statement in the loop, and we know that j==n at the end).
while j < n: [...] else: return j - i == n
could become:
while j < n: [...] return i == 0
comment:5 in reply to: ↑ 4 Changed 7 years ago by saliola
Replying to vdelecroix:
The end of the loop can be simplified (there is no break statement in the loop, and we know that j==n at the end).
while j < n: [...] else: return j - i == ncould become:
while j < n: [...] return i == 0
Done in the new patch. (If you give this new patch a positive review, then change 'needs review' to 'positive review'.)
comment:6 Changed 7 years ago by vdelecroix
- Summary changed from [with patch; needs review] speed up is_lyndon method for words to [with patch; positive review] speed up is_lyndon method for words
comment:7 Changed 7 years ago by mvngu
- Summary changed from [with patch; positive review] speed up is_lyndon method for words to [with patch, positive review] speed up is_lyndon method for words
The patch trac_6631-reviewer.patch fixes a typo introduced by trac_6631-is_lyndon.patch.
comment:8 Changed 7 years ago by mvngu
- Merged in set to Sage 4.1.2.alpha0
- Resolution set to fixed
- Reviewers changed from vdelecroix to Vincent Delecroix, Minh Van Nguyen
- Status changed from new to closed
Merged:
- trac_6631-is_lyndon.patch
- trac_6631-reviewer.patch
DO NOT APPLY!