为什么我在使用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？

- detly

Answer 1

它不会存储中间结果，但是必须存储输入值，因为每个输入值可能需要多次用于多个输出值。

由于您只能在迭代器上迭代一次，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错误。

- sth

---

感谢填写实现动机。我想绕过这个问题的唯一方法是坚持认为提供的可迭代对象也可以被复制。 - detly

我找到了问题的根源。但是如果需要product()函数的功能，有什么解决方法吗？ - DS R

@DSR 你找到了吗？ - tejasvi88

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的答案）

- Florian Brucker

---

这很有趣。我想对于这么简单的东西，我可以自己构建一个生成器。 - detly

Answer 3

我认为问题可能在于xrange返回其自己特殊的对象，这不是一个普通的可迭代对象。

xrange的实现方式（以及列表）使得你可以多次迭代该对象，而你只能对普通生成器对象进行一次迭代。因此，也许这种功能中的某些内容导致了内存错误。

- robince