Opened 10 years ago
Closed 10 years ago
#10788 closed defect (fixed)
Maximum recursion depth exceeded in the computation of return words
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | combinatorics | Keywords: | |
Cc: | jleroy | Merged in: | sage-4.7.alpha2 |
Authors: | Sébastien Labbé | Reviewers: | Julien Leroy |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
---------- Forwarded message ---------- From: Julien Leroy Date: 2011/1/19 To: Sébastien Labbé Voici quelques exemples des comportements bizarres que j'ai pu observer. A bientôt, Julien sage: TM = words.ThueMorseWord('01')[:1000] sage: TM word: 0110100110010110100101100110100110010110... sage: TM.return_words(Word('0')) set([word: 0, word: 01, word: 011]) sage: TM = words.ThueMorseWord('01')[:10000] sage: TM word: 0110100110010110100101100110100110010110... sage: TM.return_words(Word('0')) Traceback (most recent call last): ... RuntimeError: maximum recursion depth exceeded while calling a Python object sage: f = WordMorphism('a->ab,b->ba') sage: tm = f.fixed_point('a')[:1000] sage: tm word: abbabaabbaababbabaababbaabbabaabbaababba... sage: tm.return_words(Word('a')) set([word: a, word: ab, word: abb]) sage: tm = f.fixed_point('a')[:10000] sage: tm word: abbabaabbaababbabaababbaabbabaabbaababba... sage: tm.return_words(Word('a')) Traceback (most recent call last): ... IndexError: string index out of range
Attachments (1)
Change History (8)
comment:1 follow-up: ↓ 2 Changed 10 years ago by
- Cc jleroy added
- Status changed from new to needs_review
comment:2 in reply to: ↑ 1 ; follow-up: ↓ 3 Changed 10 years ago by
Replying to slabbe:
This should fix the problem. Needs review.
Hi Seb,
All test passed and it seems to fix the problem, indeed. However I have a few questions that probably come from the fact that I still don't know much about sage development.
- In most of the things that you added or modified in that patch, the functions do not contain any tests. Is there any reason for that?
- You added some "@cached_method". If I remember well, the cached_method means that what follows does not appear in the list of functions given by the "tab completion", doesn't it? However, those functions (for instance the "good_suffix_table" at line 816) do appear in that list. Am I wrong about the cached_method?
Julien
comment:3 in reply to: ↑ 2 Changed 10 years ago by
- In most of the things that you added or modified in that patch, the functions do not contain any tests. Is there any reason for that?
That's because tests were already there. In many cases, I just changed the code and kept the documentation and doctests as is.
That being said, it is true that I didn't add any tests for the problem mentionned in this ticket. I am going to add one right now and re-upload the patch.
- You added some "@cached_method". If I remember well, the cached_method means that what follows does not appear in the list of functions given by the "tab completion", doesn't it? However, those functions (for instance the "good_suffix_table" at line 816) do appear in that list. Am I wrong about the cached_method?
Cached method do and should appear in the tab completion list. A cached method means that it remembers its result instead of computing it everytime. En français, on parle de mémoization:
http://fr.wikipedia.org/wiki/M%C3%A9moization
In our case, the good_suffix_table
is consulted everytime we search for a factor. So for searching the return words of a factor, it might be a good speedup to cache (mémoiser) the good suffix table.
comment:4 follow-up: ↓ 5 Changed 10 years ago by
I just refreshed the patch. Needs review! If you have any question Julien, just ask me!
comment:5 in reply to: ↑ 4 Changed 10 years ago by
- Status changed from needs_review to positive_review
Replying to slabbe:
I just refreshed the patch. Needs review! If you have any question Julien, just ask me!
Great! All test passed and the problem is fixed. Nice job and thank you for your explicatiosn!
comment:6 Changed 10 years ago by
- Milestone changed from sage-4.6.2 to sage-4.7
- Reviewers set to Julien Leroy
comment:7 Changed 10 years ago by
- Merged in set to sage-4.7.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
This should fix the problem. Needs review.