Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#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:

Status badges

Description (last modified by slabbe)

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)

trac_13668-sl.patch (6.7 KB) - added by slabbe 10 years ago.
Tested on sage-5.2

Download all attachments as: .zip

Change History (13)

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

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

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.

Changed 10 years ago by slabbe

Tested on sage-5.2

comment:2 Changed 10 years ago by slabbe

  • 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 slabbe

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!

Last edited 10 years ago by slabbe (previous) (diff)

comment:4 Changed 10 years ago by slabbe

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 slabbe

  • Status changed from new to needs_review

comment:6 Changed 10 years ago by tjolivet

  • Authors set to Sébastien Labbé
  • 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 tjolivet

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 tjolivet

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 jdemeyer

  • Milestone changed from sage-5.4 to sage-5.5

comment:10 Changed 10 years ago by jdemeyer

  • 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 jdemeyer

  • Merged in changed from sage-5.5.beta2 to sage-5.5.beta3

comment:12 Changed 10 years ago by jdemeyer

  • Merged in changed from sage-5.5.beta3 to sage-5.5.rc0
Note: See TracTickets for help on using tickets.