#13668 closed defect (fixed)
MemoryError raised by WordMorphism.fixed_points method
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-5.5 |
Component: | combinatorics | Keywords: | |
Cc: | tjolivet | Merged in: | sage-5.5.rc0 |
Authors: | Sébastien Labbé | Reviewers: | Timo Jolivet |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The following bug was reported to me by Timo Jolivet last July 2012. It is still there is sage-5.3:
sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]}) sage: (s^7).fixed_points() [word: 122..., word: 2,3,4,...] sage: (s^7).reversal().fixed_points() MemoryError [...]
Also reported by Timo Jolivet in October 2012 the following hangs forever:
sage: s = WordMorphism("1->321331332133133,2->133321331332133133,3->2133133133321331332133133") sage: (s^2).fixed_points()
Attachments (1)
Change History (13)
comment:1 follow-up: ↓ 3 Changed 10 years ago by
comment:2 Changed 10 years ago by
- Description modified (diff)
In fact, this bugs comes from the _fixed_point_iterator
method which expand a possibly long word as a list :
sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]}) sage: s7 = s^7 sage: s7r = s7.reversal() sage: M = matrix(s7r)^10 sage: max(flatten(map(list, M))) 274861440 sage: s7r10 = s7r^10 sage: it = s7r10._fixed_point_iterator(1) sage: it.next() Traceback (most recent call last): ... in _fixed_point_iterator(self, letter) 1561 ('a', 1) 1562 """ -> 1563 w = list(self.image(letter)) 1564 while True: 1565 for a in self.image(w.pop(0)): MemoryError:
comment:3 in reply to: ↑ 1 Changed 10 years ago by
It might be related to the bug in the description of this ticket... I will wait until a solution is found for the first before creating a new ticket for the second as the solution might fix both.
Indeed, the solution (which make use of iterators instead of lists) fixes both problems. I just attached a patch. Needs review!
comment:4 Changed 10 years ago by
Moreover, I am getting some timing improvements due to the change of the code of fixed_points
method which do not depend anymore on the periodic_points
method :
BEFORE:
sage: f = WordMorphism('a->ab,b->cab,c->bcc') sage: %timeit f.fixed_points() 125 loops, best of 3: 2.1 ms per loop
AFTER:
sage: f = WordMorphism('a->ab,b->cab,c->bcc') sage: %timeit f.fixed_points() 625 loops, best of 3: 340 µs per loop
comment:5 Changed 10 years ago by
- Status changed from new to needs_review
comment:6 Changed 10 years ago by
- Milestone changed from sage-5.5 to sage-5.4
- Reviewers set to Timo Jolivet
- Status changed from needs_review to positive_review
comment:7 Changed 10 years ago by
I don't have any problematic examples anymore and the patch changes are simple and effective, so positive review.
comment:8 Changed 10 years ago by
Note that this patch also fixes the following problem, thanks to better implementation:
sage: s = WordMorphism({1:[1,2],2:[2,3],3:[4],4:[5],5:[6],6:[7],7:[8],8:[9],9:[10],10:[1]}) sage: (s.reversal()^7).fixed_points() MemoryError [...]
comment:9 Changed 10 years ago by
- Milestone changed from sage-5.4 to sage-5.5
comment:10 Changed 10 years ago by
- Merged in set to sage-5.5.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:11 Changed 10 years ago by
- Merged in changed from sage-5.5.beta2 to sage-5.5.beta3
comment:12 Changed 10 years ago by
- Merged in changed from sage-5.5.beta3 to sage-5.5.rc0
Also reported by Timo Jolivet in October 2012 the following hangs forever:
It might be related to the bug in the description of this ticket... I will wait until a solution is found for the first before creating a new ticket for the second as the solution might fix both.