Dlaczego otrzymuję MemoryError z itertools.product?

Question

Spodziewam się następujący fragment dać mi iterację plonowania par od iloczynu kartezjańskiego dwóch wejściowych iterables:

$ 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 

zamian dostaję MemoryError. Ale myślałem, że itertools.product nie zapisuje wyników pośrednich w pamięci, więc co jest przyczyną MemoryError?

Answer 1

Nie przechowuje pośrednich wyników, ale musi przechowywać wartości wejściowe, ponieważ każda z nich może być potrzebna kilka razy dla kilku wartości wyjściowych.

Ponieważ można tylko iteracyjne raz na iteratora, product nie mogą być realizowane równoważne to:

def prod(a, b): 
    for x in a: 
    for y in b: 
     yield (x, y) 

Jeśli tutaj b jest iterator, to zostanie wyczerpany po pierwszej iteracji pętli zewnętrznej i nie więcej elementów będzie produkowanych w kolejnych wykonaniach for y in b.

product radzi sobie z tym problemem poprzez przechowywanie wszystkich elementów, które są produkowane przez b, dzięki czemu można je stosować wielokrotnie:

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) 

w rzeczywistości product próbuje przechowywać elementy produkowane przez wszystkich iterables to jest podana, mimo że można tego uniknąć przy pierwszym parametrze. Funkcja musi najpierw przejść tylko przez pierwszą iterację, więc nie będzie musiała buforować tych wartości. Ale i tak próbuje to zrobić, co prowadzi do tego, że widzisz.

Answer 2

nie przechowuje produktów pośrednich w pamięci, ale przechowuje wersje tuple oryginalnych iteratorów.

Można to zobaczyć, patrząc na źródło modułu itertools. Znajduje się w pliku Modules/itertoolsmodule.c w źródłowej dystrybucji Python 2.7.2. Tam znajdziemy w funkcji product_new (w zasadzie konstruktora dla obiektu product) z linii 1828 roku:

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; 
} 

w tym kodzie, args są argumenty product. W trzecim wierszu tego fragmentu kodu argument i th jest konwertowany na krotkę. W związku z tym kod próbuje przekształcić iterator xrange(0, 10**9) w krotkę, co daje w wyniku MemoryError.

Nie jestem pewien, dlaczego zachowuje się tak: itertools.product. Zamiast zapisywania każdego iteratora wejściowego jako krotki, powinno wystarczyć przechowywanie ostatniego elementu zwróconego z każdego iteratora. (EDYCJA: Zobacz odpowiedź na pytanie z tego powodu)

Answer 3

Myślę, że problemem może być to, że xrange zwraca swój własny specjalny rodzaj obiektu, który nie jest normalną iteracją.

xrange jest zaimplementowany w taki sposób (jak listy), które można wielokrotnie powtarzać nad obiektem, , podczas gdy można powtórzyć normalny obiekt generatora tylko raz. Być może coś z tej funkcji jest odpowiedzialne za błąd pamięci.