Почему я получаю MemoryError с itertools.product?

Я ожидаю, что следующий фрагмент даст мне итератор, дающий пары из декартова произведения двух входных итераций:

$ 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

Вместо этого я получаю a MemoryError. Но я думал, что itertools.product не сохранил промежуточные результаты в памяти, поэтому что вызывает MemoryError?

Ответ 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, который вы видите.

Ответ 2

itertools.product не сохраняет промежуточные продукты в памяти, но хранит версии исходных итераторов tuple.

Это можно увидеть, посмотрев на источник модуля itertools. Он находится в файле Modules/itertoolsmodule.c в исходном дистрибутиве Python 2.7.2. Там мы находим в функции product_new (в основном конструктор объекта product) строки 1828 и далее:

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 th преобразуется в кортеж. Следовательно, код пытается преобразовать ваш итератор xrange(0, 10**9) в кортеж, в результате получится MemoryError.

Я не уверен, почему itertools.product ведет себя так. Вместо того, чтобы хранить каждый итератор ввода как кортеж, этого должно быть достаточно для хранения последнего элемента, возвращаемого с каждого итератора. (РЕДАКТИРОВАТЬ: см. Ответ "за" по этой причине)

Ответ 3

Я думаю, проблема может заключаться в том, что xrange возвращает свой собственный особый тип объекта, который не является нормальным итерабельным.

xrange реализуется таким образом (как и списки), который вы можете многократно перебирать по объекту, в то время как вы можете перебирать обычный объект генератора только один раз. Поэтому, возможно, что-то из этой функции отвечает за ошибку памяти.