为什么在使用itertools.product时会出现MemoryError？

Question

我本来以为下面这段代码可以给我一个迭代器，输出两个输入可迭代对象的笛卡尔积的配对：

$ 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

但是，我却遇到了一个MemoryError（内存错误）。我记得itertools.product这个工具并不会把中间结果存储在内存里，那为什么会出现MemoryError呢？

Answer 1

我觉得问题可能出在xrange返回了一种特殊的对象，这种对象不是普通的可迭代对象。

xrange的实现方式和列表类似，你可以多次遍历这个对象，而普通的生成器对象只能遍历一次。所以，也许正是这种功能导致了内存错误。

Answer 2

itertools.product 这个工具不会把中间的结果都存到内存里，但它会把原始的迭代器转换成 tuple（元组）形式存起来。

你可以通过查看 itertools 模块的源代码来理解这一点。这个源代码在 Python 2.7.2 的文件 Modules/itertoolsmodule.c 中。在这里，我们可以看到从第 1828 行开始的 product_new 函数（也就是 product 对象的构造函数）：

for (i=0; i < nargs ; ++i) {
    PyObject *item = PyTuple_GET_ITEM(args, i);
    PyObject *pool = PySequence_Tuple(item);
    if (pool == NULL)
        goto error;
    PyTuple_SET_ITEM(pools, i, pool);
    indices[i] = 0;
}

在这段代码中，args 是传给 product 的参数。在这段代码的第三行，i 这个参数被转换成了一个元组。因此，代码试图把你的迭代器 xrange(0, 10**9) 转换成元组，这样就会导致 MemoryError（内存错误）。

我不太明白为什么 itertools.product 会这样处理。与其把每个输入的迭代器都存成元组，存下每个迭代器最后返回的那个项目就够了。(编辑：可以参考 sth 的回答了解原因)

Answer 3

它不存储中间的结果，但是必须保存输入值，因为这些输入值可能会被多次使用来计算多个输出值。

由于你只能对一个迭代器进行一次遍历，product 不能像这样实现：

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

如果这里的 b 是一个迭代器，那么在外层循环的第一次迭代后，它就会被耗尽，之后再执行 for y in b 时就不会再产生任何元素了。

product 通过保存 b 产生的所有元素来解决这个问题，这样就可以多次使用这些元素：

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)

实际上，product 尝试保存它所接收的所有可迭代对象产生的元素，尽管对于它的第一个参数，这种做法是可以避免的。这个函数只需要遍历第一个可迭代对象一次，所以其实不需要缓存那些值。但它还是尝试这么做，这就导致了你看到的 MemoryError。