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:

Status badges

Description (last modified by evandomme)

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 evandomme

  • Branch set to u/evandomme/critical_exponent_for_words

comment:2 Changed 4 years ago by evandomme

  • Commit set to 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8
  • Status changed from new to needs_review

New commits:

​7a3c121Better critical exponent

comment:3 Changed 4 years ago by evandomme

  • Type changed from PLEASE CHANGE to enhancement

comment:4 Changed 4 years ago by evandomme

  • Description modified (diff)

comment:5 Changed 4 years ago by vdelecroix

Impressive timings! Cool :-)

comment:6 Changed 4 years ago by vdelecroix

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 git

  • Commit changed from 7a3c1214c0dfdf9d21db02c3e978c28abfc920e8 to da0b349a94de17b3e96cf4c7cb3f41cbf48dd769

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

​da0b349Modification according to comment 6 (raise an error for the empty word)

comment:8 Changed 4 years ago by vdelecroix

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
Last edited 4 years ago by vdelecroix (previous) (diff)

comment:9 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:10 follow-up: Changed 4 years ago by slabbe

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 vdelecroix

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).

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

comment:12 Changed 4 years ago by vdelecroix

  • 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

rebased on beta6

New commits:

​5cf1cc5Better critical exponent
​adc11ebModification according to comment 6 (raise an error for the empty word)
​8a3717cFix error message

comment:13 Changed 4 years ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to positive_review

comment:14 Changed 4 years ago by vdelecroix

Merci Sébastien!

comment:15 Changed 4 years ago by vbraun

  • Branch changed from u/vdelecroix/25525 to 8a3717ca6bf49989b9da1a2656487b3cf6c3b723
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.