Re: itertools product(infinite iterator) hangs
On Sat, 14 Sep 2019 at 07:22, ast wrote:
>
> Le 14/09/2019 à 04:26, Oscar Benjamin a écrit :
> >
> > What am I missing?
>
> here is a pseudo code for product:
>
> def product(*args, repeat=1):
> # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
> # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
> pools = [tuple(pool) for pool in args] * repeat
> result = [[]]
> for pool in pools:
> result = [x+[y] for x in result for y in pool]
> for prod in result:
> yield tuple(prod)
>
> clearly "tuple(pool)" hangs with an infinite iterable pool
Thanks for this response. I also realised this myself after a while.
Actually I didn't see your message until I posted my own followup
reply because gmail had moved it into spam. Apparently it doesn't like
the headers in your email for some reason: "Gmail could not verify
that it actually came from gmail.com. Avoid clicking links,
downloading attachments or replying with personal information."
Oscar
--
https://mail.python.org/mailman/listinfo/python-list
Re: itertools product(infinite iterator) hangs
On Sat, 14 Sep 2019 at 03:26, Oscar Benjamin wrote: > > I've been staring at this for a little while: > > from itertools import product > > class Naturals: > def __iter__(self): > i = 1 > while True: > yield i > i += 1 > > N = Naturals() > print(iter(N)) > print(product(N)) # <--- hangs > > When I run the above the call to product hangs but I can't see why. There is already an issue for this: https://bugs.python.org/issue10109 It seems product always consumes all of its iterators entirely before yielding anything (in fact before even iter is called). That seemed surprising to me when looking at the trivial case of a product of one iterable since in *that* case it is clearly unnecessary. I wrote my own versions that get around this. This is a simple version: def iproduct_simple(*iterables): '''Returns the Cartesian product of iterables but doesn't hang for infinite iterators''' if len(iterables) == 0: yield () return first, others = iterables[0], iterables[1:] for f in first: for o in iprod(*others): yield (f,) + o This gives output in normal order for finite inputs and doesn't hang in the case of infinite inputs. However if any of the inputs is infinite iproduct_simple won't actually yield all elements. So I made a more complicated version that yields all possibilities (analogous to enumerating rational numbers): def iproduct(*iterables): '''Returns Cartesian product of iterables. Yields every element eventually''' if len(iterables) == 0: yield () return elif len(iterables) == 1: for e in iterables[0]: yield (e,) elif len(iterables) == 2: for e12 in iproduct2(*iterables): yield e12 else: first, others = iterables[0], iterables[1:] for ef, eo in iproduct2(first, iprod(*others)): yield (ef,) + eo def iproduct2(iterable1, iterable2): '''Cartesian product of two possibly infinite iterables''' it1 = iter(iterable1) it2 = iter(iterable2) elems1 = [] elems2 = [] sentinel = object() def append(it, elems): e = next(it, sentinel) if e is not sentinel: elems.append(e) n = 0 append(it1, elems1) append(it2, elems2) while n <= len(elems1) + len(elems2): for m in range(n-len(elems1)+1, len(elems2)): yield (elems1[n-m], elems2[m]) n += 1 append(it1, elems1) append(it2, elems2) -- Oscar -- https://mail.python.org/mailman/listinfo/python-list
Re: itertools product(infinite iterator) hangs
Le 14/09/2019 à 04:26, Oscar Benjamin a écrit :
I've been staring at this for a little while:
from itertools import product
class Naturals:
def __iter__(self):
i = 1
while True:
yield i
i += 1
N = Naturals()
print(iter(N))
print(product(N)) # <--- hangs
When I run the above the call to product hangs but I can't see why. I
would expect that since I'm not iterating over the product it would
just call iter(N) but clearly not since iter(N) returns a generator
instantly where as product(N) hangs.
What am I missing?
Oscar
here is a pseudo code for product:
def product(*args, repeat=1):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = [tuple(pool) for pool in args] * repeat
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
clearly "tuple(pool)" hangs with an infinite iterable pool
--
https://mail.python.org/mailman/listinfo/python-list
itertools product(infinite iterator) hangs
I've been staring at this for a little while: from itertools import product class Naturals: def __iter__(self): i = 1 while True: yield i i += 1 N = Naturals() print(iter(N)) print(product(N)) # <--- hangs When I run the above the call to product hangs but I can't see why. I would expect that since I'm not iterating over the product it would just call iter(N) but clearly not since iter(N) returns a generator instantly where as product(N) hangs. What am I missing? Oscar -- https://mail.python.org/mailman/listinfo/python-list
