On 15.06.2012 09:00, Paul Rubin wrote: > Alexander Blinne <n...@blinne.net> writes: >>> def gen_s(): >>> s = [1] >>> m = skipdups(heapq.merge(*[(lambda j: (k*j for k in s))(n) for n in >>> [2,3,5]])) >>> yield s[0] >>> while True: >>> k = m.next() >>> s.append(k) >>> yield k > > Nice. I wouldn't have been sure that "for k in s" worked properly when > s was changing like that.
I just tried it and it worked. Not sure if it is guaranteed. > There is a space complexity problem compared to the Scheme or Haskell > version: all the s[i]'s are saved in the s array, instead of being > discarded once they are yielded. That means generating n elements needs > O(n) space instead of O(n**0.7) or something like that. I guess you can > get around it with collections.deque instead of a list. An Element of s could be discarded, after every one of the three (k*j for k in s)-generators went over it. I don't think that this is possible with one deque (at least with the built-in merger of heapq, a self-written one could be adapted). Storing everything three times (one deque for every generator) would be a mess as well. "Manual" garbage collection could be done by discarding all elements smaller one fifth of the current element of s, because the three generators already went by them. This could be done with a deque. How do Haskell or Scheme determine when elements are not longer needed? Greetings -- http://mail.python.org/mailman/listinfo/python-list
