Improving factor complexity of words functions

[seblabbe]

Improving the word complexity functions by

• caching palindromic_lacunas_study
• caching suffix_tree
• caching suffix_trie
• allowing factor_set to take an integer as input
• adding rauzy_graph function for finite word

CC: @videlec

Component: combinatorics

Keywords: factor complexity

Author: Sébastien Labbé

Reviewer: Vincent Delecroix

Merged: sage-4.2.1.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/7227

[seblabbe]

Attachment: trac_7227_word_factor_complexity-sl.patch.gz

[seblabbe]

comment:1

Here are some examples of the improvements made by the patch :

BEFORE:

sage: t = words.ThueMorseWord()
sage: w = t[:10000]
sage: time _ = [w.number_of_factors(i) for i in range(20)]
CPU times: user 4.19 s, sys: 0.00 s, total: 4.19 s
Wall time: 4.19 s
sage: time _ = [w.number_of_factors(i) for i in range(50)]
CPU times: user 10.28 s, sys: 0.00 s, total: 10.28 s
Wall time: 10.28 s

AFTER:

sage: t = words.ThueMorseWord()
sage: w = t[:10000]
sage: time _ = [w.number_of_factors(i) for i in range(20)]
CPU times: user 0.30 s, sys: 0.00 s, total: 0.30 s
Wall time: 0.30 s
sage: time _ = [w.number_of_factors(i) for i in range(50)]
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
sage: time _ = [w.number_of_factors(i) for i in range(100)]
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
sage: time _ = [w.number_of_factors(i) for i in range(1000)]
CPU times: user 4.90 s, sys: 0.00 s, total: 4.90 s
Wall time: 4.90 s
sage: time _ = [w.number_of_factors(i) for i in range(1001)]
CPU times: user 4.85 s, sys: 0.00 s, total: 4.85 s
Wall time: 4.85 s
sage: time _ = [w.number_of_factors(i) for i in range(2000)]
CPU times: user 27.64 s, sys: 0.00 s, total: 27.64 s
Wall time: 27.64 s

I should also add some Rauzy graphs examples and some timing improvements on palindrome complexity as well.

[seblabbe]

Attachment: trac_7227_edge_labels-sl.patch.gz

[seblabbe]

comment:2

I added a patch that improves the rauzy graph function (adds the labels to the edges).

Still needs review!

[videlec]

comment:3

rauzy_graph : why don't you use DiGraph method for the creation of edges ?

The rest is OK.

[videlec]

Reviewer: vdelecroix

[seblabbe]

comment:5

Replying to @videlec:

rauzy_graph : why don't you use DiGraph method for the creation of edges ?

You mean the add_edge method? I don't know. Is it faster?

[videlec]

comment:6

Replying to @seblabbe:

Replying to @videlec:

rauzy_graph : why don't you use DiGraph method for the creation of edges ?

You mean the add_edge method? I don't know. Is it faster?

At least it is not slower and I find it clearer:

sage: timeit('G = DiGraph(loops=True)\nfor i in range(200):\n  for j in range(200):\n    d.add_edge(i,j)')
5 loops, best of 3: 248 ms per loop
sage: timeit('d = {}\nfor i in range(200):\n  d[i]=[]\n  for j in range(200):\n    d[i].append(j)\nG=DiGraph(d,loops=True)')
5 loops, best of 3: 266 ms per loop

[seblabbe]

Attachment: trac_7227_add_edge-sl.patch.gz

Applies over the precedent 2 patches.

[seblabbe]

comment:7

Thanks for the suggestion Vincent. I did the changes. I also changed the behavior for n=0 to agree with what is currently done in digraphs.DeBruijn() (see #7246).

Needs review!

[videlec]

comment:8

Positive review.

Remark for future: the graph rendering is quite bad because word renders "word: xxxx"

[seblabbe]

comment:9

Remark for future: the graph rendering is quite bad because word renders "word: xxxx"

One way to avoid the word: identifier is to set it empty using

sage: WordOptions(identifier='')
sage: Word(range(10))
0123456789

but it affects not only the vertices of the Rauzy graph but every single print of a word which might not be exactly what you want...

[mwhansen]

Merged: sage-4.2.1.alpha0

[mwhansen]

Changed reviewer from vdelecroix to Vincent Delecroix

[mwhansen]

Author: Sebastien Labbe

[fchapoton]

Changed author from Sebastien Labbe to Sébastien Labbé