Opened 6 years ago

Closed 6 years ago

# [with patch, positive review] speed up is_lyndon method for words

Reported by: Owned by: saliola Franco Saliola major sage-4.1.2 combinatorics words slabbe Sage 4.1.2.alpha0 Franco Saliola Vincent Delecroix, Minh Van Nguyen

### 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
```

DO NOT APPLY!

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

• Reviewers set to vdelecroix

### comment:4 follow-up: ↓ 5 Changed 6 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 6 years ago by saliola

depends on #6627;

### comment:5 in reply to: ↑ 4 Changed 6 years ago by saliola

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 6 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 6 years ago by mvngu

reviewer patch: fixes typo

### comment:7 Changed 6 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 6 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.