Le mardi 25 Janvier 2005 09:01, Michael Spencer a ÃcritÂ: > Francis Girard wrote: > > 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 : > > Thanks, Francis and Jeff for raising a fascinating topic. I've enjoyed > trying to get my head around both the algorithm and your non-recursive > implementation. >
Yes, it's been fun. > Here's a version of your implementation that uses a helper class to make > the algorithm itself prettier. > > from itertools import tee, imap > > def hamming(): > def _hamming(): > yield 1 > for n in imerge(2 * hamming, imerge(3 * hamming, 5 * hamming)): > yield n > > hamming = Tee(_hamming()) > return iter(hamming) > > > class Tee(object): > """Provides an indepent iterator (using tee) on every iteration > request Also implements lazy iterator arithmetic""" > def __init__(self, iterator): > self.iter = tee(iterator,1)[0] > def __iter__(self): > return self.iter.__copy__() > def __mul__(self, number): > return imap(lambda x: x * number,self.__iter__()) > > 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: # if y < x: > yield y > y = ys.next() > > >>> hg = hamming() > >>> for i in range(10000): > > ... n = hg.next() > ... if i % 1000 == 0: print i, n > ... > 0 1 > 1000 51840000 > 2000 8100000000 > 3000 279936000000 > 4000 4707158941350 > 5000 50960793600000 > 6000 409600000000000 > 7000 2638827906662400 > 8000 14332723200000000 > 9000 68024448000000000 > > Interesting idea. > Regards > > Michael -- http://mail.python.org/mailman/listinfo/python-list
