Opened 4 years ago
Closed 4 years ago
#25525 closed enhancement (fixed)
Critical exponent for words
Reported by: | evandomme | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.3 |
Component: | combinatorics | Keywords: | MathExp2018, thursdaysbdx |
Cc: | vdelecroix, slabbe | Merged in: | |
Authors: | Vincent Delecroix, Élise Vandomme | Reviewers: | Sébastien Labbé |
Report Upstream: | N/A | Work issues: | |
Branch: | 8a3717c (Commits, GitHub, GitLab) | Commit: | 8a3717ca6bf49989b9da1a2656487b3cf6c3b723 |
Dependencies: | Stopgaps: |
Description (last modified by )
We improve the algorithm computing the critical exponent for words.
For instance, consider the critical exponent of the length-1000 prefix of the Fibonacci word,
fibo = words.FibonacciWord()[:1000] % time fibo.critical_exponent()
Before it took:
CPU times: user 1min 19s, sys: 398 ms, total: 1min 19s
Wall time: 1min 20s
173/48
Now, it takes:
CPU times: user 1.3 s, sys: 64.1 ms, total: 1.36 s
Wall time: 1.34 s.
173/48
Change History (15)
comment:1 Changed 4 years ago by
- Branch set to u/evandomme/critical_exponent_for_words
comment:2 Changed 4 years ago by
- Commit set to 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8
- Status changed from new to needs_review
comment:3 Changed 4 years ago by
- Type changed from PLEASE CHANGE to enhancement
comment:4 Changed 4 years ago by
- Description modified (diff)
comment:5 Changed 4 years ago by
Impressive timings! Cool :-)
comment:6 Changed 4 years ago by
This following line can be removed
m = 0
(since m
is later initialized with m = pft[l-j+k-2]
before it is used)
It would be nice to add a little bit of comment in the code
pft = [0] * wlen # the prefix function table queue = [(0, 0, -1, 0)] # suffix tree vertices to visit for DFS best_exp = 1 # best exponent so far
You can replace w
with self
instead of having two variables pointing to the same object.
What should be the critical exponent of the empty word? (I guess the function currently returns 1
but should rather raise an error). There should be a doctest for this.
comment:7 Changed 4 years ago by
- Commit changed from 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8 to da0b349a94de17b3e96cf4c7cb3f41cbf48dd769
Branch pushed to git repo; I updated commit sha1. New commits:
da0b349 | Modification according to comment 6 (raise an error for the empty word)
|
comment:8 Changed 4 years ago by
The syntax
raise ValueError, 'The empty word has no critical exponent.'
is valid in Python2 but not Python3. To prepare the future, use
raise ValueError('The empty word has no critical exponent.')
(which is Python2 and Python3 valid).
And convention for the error messages: keep it short, start with a lower case and no punctuation. Similar to
sage: l = [] sage: l[1] sage: l = [] sage: l[1] Traceback (most recent call last): ... IndexError: list index out of range
comment:9 Changed 4 years ago by
- Status changed from needs_review to needs_work
comment:10 follow-up: ↓ 11 Changed 4 years ago by
Is it possible to add a reference in the documentation of the method to the article where this algorithm is defined?
I have time this morning to review the code. Otherwise, I will review it next Thursday.
comment:11 in reply to: ↑ 10 Changed 4 years ago by
Replying to slabbe:
Is it possible to add a reference in the documentation of the method to the article where this algorithm is defined?
The algorithm is the same as before. It is just more efficiently done. You just go through all factors of the word and compute the exponent. The version in this branch is better because
- instead of running through the factors it performs a depth first search in the suffix tree
- it does not build the factors, it simply updates the prefix function table
I have time this morning to review the code. Otherwise, I will review it next Thursday.
comment:8 should be addressed before review (status is needs_work).
comment:12 Changed 4 years ago by
- Branch changed from u/evandomme/critical_exponent_for_words to u/vdelecroix/25525
- Commit changed from da0b349a94de17b3e96cf4c7cb3f41cbf48dd769 to 8a3717ca6bf49989b9da1a2656487b3cf6c3b723
- Status changed from needs_work to needs_review
comment:13 Changed 4 years ago by
- Reviewers set to Sébastien Labbé
- Status changed from needs_review to positive_review
comment:14 Changed 4 years ago by
Merci Sébastien!
comment:15 Changed 4 years ago by
- Branch changed from u/vdelecroix/25525 to 8a3717ca6bf49989b9da1a2656487b3cf6c3b723
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
Better critical exponent