python - Why do I get a MemoryError with itertools.product?

Question

I would expect the following snippet to give me an iterator yielding pairs from the Cartesian product of the two input iterables:

$ python
Python 2.7.1+ (r271:86832, Apr 11 2011, 18:13:53) 
[GCC 4.5.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import itertools
>>> one = xrange(0, 10**9)
>>> two = (1,)
>>> prods = itertools.product(one, two)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

Instead, I get a MemoryError. But I thought that itertools.product did not store the intermediate results in memory, so what's causing the MemoryError?

Answer 1

It doesn't store intermediate results, but it has to store the input values because each of those might be needed several times for several output values.

Since you can only iterate once over an iterator, product cannot be implemented equivalent to this:

def prod(a, b):
  for x in a:
    for y in b:
       yield (x, y)

If here b is an iterator, it will be exhausted after the first iteration of the outer loop and no more elements will be produced in subsequent executions of for y in b.

product works around this problem by storing all the elements that are produced by b, so that they can be used repeatedly:

def prod(a, b):
  b_ = tuple(b)  # create tuple with all the elements produced by b
  for x in a:
    for y in b_:
       yield (x, y)

In fact, product tries to store the elements produced by all the iterables it is given, even though that could be avoided for its first parameter. The function only needs to walk over the first iterable once, so it wouldn't have to cache those values. But it tries to do anyway, which leads to the MemoryError you see.