The following implementation is even more speaking as it makes self-evident
and almost mechanical how to translate algorithms that run after their tail
from recursion to "tee" usage :
*** BEGIN SNAP
from itertools import tee, imap
import sys
def imerge(xs, ys):
x = xs.next()
y = ys.next()
while True:
if x == y:
yield x
x = xs.next()
y = ys.next()
elif x < y:
yield x
x = xs.next()
else:
yield y
y = ys.next()
def hamming():
def _hamming():
yield 1
hamming2 = hammingGenerators[0]
hamming3 = hammingGenerators[1]
hamming5 = hammingGenerators[2]
for n in imerge(imap(lambda h: 2*h, iter(hamming2)),
imerge(imap(lambda h: 3*h, iter(hamming3)),
imap(lambda h: 5*h, iter(hamming5)))):
yield n
hammingGenerators = tee(_hamming(), 4)
return hammingGenerators[3]
for i in hamming():
print i,
sys.stdout.flush()
*** END SNAP
Here's an implementation of the fibonacci sequence that uses "tee" :
*** BEGIN SNAP
from itertools import tee
import sys
def fib():
def _fib():
yield 1
yield 1
curGen = fibGenerators[0]
curAheadGen = fibGenerators[1]
curAheadGen.next()
while True:
yield curGen.next() + curAheadGen.next()
fibGenerators = tee(_fib(), 3)
return fibGenerators[2]
for n in fib():
print n,
sys.stdout.flush()
*** END SNAP
Francis Girard
FRANCE
Le lundi 24 Janvier 2005 14:09, Francis Girard a ÃcritÂ:
> Ok, I think that the bottom line is this :
>
> For all the algorithms that run after their tail in an FP way, like the
> Hamming problem, or the Fibonacci sequence, (but unlike Sieve of
> Eratosthene -- there's a subtle difference), i.e. all those algorithms that
> typically rely upon recursion to get the beginning of the generated
> elements in order to generate the next one ...
>
> ... so for this family of algorithms, we have, somehow, to abandon
> recursion, and to explicitely maintain one or many lists of what had been
> generated.
>
> One solution for this is suggested in "test_generators.py". But I think
> that this solution is evil as it looks like recursion is used but it is not
> and it depends heavily on how the m235 function (for example) is invoked.
> Furthermore, it is _NOT_ memory efficient as pretended : it leaks ! It
> internally maintains a lists of generated results that grows forever while
> it is useless to maintain results that had been "consumed". Just for a
> gross estimate, on my system, percentage of memory usage for this program
> grows rapidly, reaching 21.6 % after 5 minutes. CPU usage varies between
> 31%-36%. Ugly and inefficient.
>
> The solution of Jeff Epler is far more elegant. The "itertools.tee"
> function does just what we want. It internally maintain a list of what had
> been generated and deletes the "consumed" elements as the algo unrolls. To
> follow with my gross estimate, memory usage grows from 1.2% to 1.9% after 5
> minutes (probably only affected by the growing size of Huge Integer). CPU
> usage varies between 27%-29%.
> Beautiful and effecient.
>
> You might think that we shouldn't be that fussy about memory usage on
> generating 100 digits numbers but we're talking about a whole family of
> useful FP algorithms ; and the best way to implement them should be
> established.
>
> For this family of algorithms, itertools.tee is the way to go.
>
> I think that the semi-tutorial in "test_generators.py" should be updated to
> use "tee". Or, at least, a severe warning comment should be written.
>
> Thank you,
>
> Francis Girard
> FRANCE
>
> Le dimanche 23 Janvier 2005 23:27, Jeff Epler a ÃcritÂ:
> > Your formulation in Python is recursive (hamming calls hamming()) and I
> > think that's why your program gives up fairly early.
> >
> > Instead, use itertools.tee() [new in Python 2.4, or search the internet
> > for an implementation that works in 2.3] to give a copy of the output
> > sequence to each "multiply by N" function as well as one to be the
> > return value.
> >
> > Here's my implementation, which matched your list early on but
> > effortlessly reached larger values. One large value it printed was
> > 6412351813189632 (a Python long) which indeed has only the distinct
> > prime factors 2 and 3. (2**43 * 3**6)
> >
> > Jeff
> >
> > from itertools import tee
> > import sys
> >
> > def imerge(xs, ys):
> > x = xs.next()
> > y = ys.next()
> > while True:
> > if x == y:
> > yield x
> > x = xs.next()
> > y = ys.next()
> > elif x < y:
> > yield x
> > x = xs.next()
> > else:
> > yield y
> > y = ys.next()
> >
> > def hamming():
> > def _hamming(j, k):
> > yield 1
> > hamming = generators[j]
> > for i in hamming:
> > yield i * k
> > generators = []
> > generator = imerge(imerge(_hamming(0, 2), _hamming(1, 3)),
> > _hamming(2, 5)) generators[:] = tee(generator, 4)
> > return generators[3]
> >
> > for i in hamming():
> > print i,
> > sys.stdout.flush()
--
http://mail.python.org/mailman/listinfo/python-list
