Почему я получаю 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

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

Источник

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 ты видишь.

Источник

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

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

Источник

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

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

Источник
Другие вопросы по тегам