Opened 5 years ago

Closed 5 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)

trac_6631-is_lyndon.2.patch (2.6 KB) - added by saliola 5 years ago.
DO NOT APPLY!
trac_6631-is_lyndon.patch (2.6 KB) - added by saliola 5 years ago.
depends on #6627;
trac_6631-reviewer.patch (694 bytes) - added by mvngu 5 years ago.
reviewer patch: fixes typo

Download all attachments as: .zip

Change History (11)

Changed 5 years ago by saliola

DO NOT APPLY!

comment:1 Changed 5 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 5 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 5 years ago by vdelecroix

  • Reviewers set to vdelecroix

comment:4 follow-up: Changed 5 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

Changed 5 years ago by saliola

depends on #6627;

comment:5 in reply to: ↑ 4 Changed 5 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 == n

could 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 5 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

Changed 5 years ago by mvngu

reviewer patch: fixes typo

comment:7 Changed 5 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 5 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:

  1. trac_6631-is_lyndon.patch
  2. trac_6631-reviewer.patch
Note: See TracTickets for help on using tickets.