#7227 closed enhancement (fixed)
[with patch] Improving factor complexity of words functions
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-4.2.1 |
Component: | combinatorics | Keywords: | factor complexity |
Cc: | vdelecroix | Merged in: | sage-4.2.1.alpha0 |
Authors: | Sébastien Labbé | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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
Attachments (3)
Change History (14)
Changed 12 years ago by
comment:1 Changed 12 years ago by
- Status changed from new to needs_review
- Summary changed from Improving factor complexity of words functions to [with patch, needs review] Improving factor complexity of words functions
Changed 12 years ago by
comment:2 Changed 12 years ago by
- Cc vdelecroix added
I added a patch that improves the rauzy graph function (adds the labels to the edges).
Still needs review!
comment:3 follow-up: ↓ 5 Changed 12 years ago by
- Reviewers set to vdelecroix
- Summary changed from [with patch, needs review] Improving factor complexity of words functions to [with patch] Improving factor complexity of words functions
rauzy_graph : why don't you use DiGraph? method for the creation of edges ?
The rest is OK.
comment:4 Changed 12 years ago by
- Summary changed from [with patch] Improving factor complexity of words functions to [with patch, needs review] Improving factor complexity of words functions
comment:5 in reply to: ↑ 3 ; follow-up: ↓ 6 Changed 12 years ago by
Replying to vdelecroix:
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?
comment:6 in reply to: ↑ 5 Changed 12 years ago by
Replying to slabbe:
Replying to vdelecroix:
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
comment:7 Changed 12 years ago by
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!
comment:8 follow-up: ↓ 9 Changed 12 years ago by
- Status changed from needs_review to positive_review
- Summary changed from [with patch, needs review] Improving factor complexity of words functions to [with patch] Improving factor complexity of words functions
Positive review.
Remark for future: the graph rendering is quite bad because word renders "word: xxxx"
comment:9 in reply to: ↑ 8 Changed 12 years ago by
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...
comment:10 Changed 12 years ago by
- Merged in set to sage-4.2.1.alpha0
- Resolution set to fixed
- Reviewers changed from vdelecroix to Vincent Delecroix
- Status changed from positive_review to closed
comment:11 Changed 5 years ago by
- Report Upstream set to N/A
Here are some examples of the improvements made by the patch :
BEFORE:
AFTER:
I should also add some Rauzy graphs examples and some timing improvements on palindrome complexity as well.