Почему я получаю MemoryError с itertools.product? - PullRequest
Новая
       13

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

13 голосов
/ 02 января 2012

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

$ 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 ]

16 голосов
/ 02 января 2012

Он не хранит промежуточные результаты , но должен хранить входные значения, поскольку каждое из них может понадобиться несколько раз для нескольких выходных значений.

Поскольку вы можете выполнять итерацию только один раз, 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, который вы видите.

7 голосов
/ 02 января 2012

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 ведет себя так. Вместо того, чтобы хранить каждый входной итератор как кортеж, этого должно быть достаточно для сохранения последнего элемента, возвращаемого каждым итератором. (РЕДАКТИРОВАТЬ: см. Sh ответ по причине)

0 голосов
/ 02 января 2012

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

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

...