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

它不存储中间结果,但必须存储输入值,因为对于多个输出值,可能需要多次输入值.

由于您只能在迭代器上迭代一次,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你看到了.

Answer 2

itertools.product不会将中间产品存储在内存中,但它会存储tuple原始迭代器的版本.

通过查看itertools模块的来源可以看出这一点.它位于Modules/itertoolsmodule.cPython 2.7.2源代码分发的文件中.我们在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.在此代码段的第三行中,ith参数转换为元组.因此,代码尝试将迭代器转换xrange(0, 10**9)为元组,从而产生一个MemoryError.

我不确定为什么itertools.product会这样.不是将每个输入迭代器存储为元组,而是应该足以存储从每个迭代器返回的最后一个项.(编辑:看到某事的答案)