¿Por qué obtengo un MemoryError con itertools.product?

Question

yo esperaría que el siguiente fragmento que me diera un iterador produciendo pares del producto cartesiano de los dos iterables de entrada:

$ 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 

En cambio, aparece un MemoryError. Pero pensé que itertools.product no almacenaba los resultados intermedios en la memoria, entonces, ¿qué está causando el MemoryError?

Answer 1

No almacena los resultados intermedios , pero tiene que almacenar los valores de entrada porque cada uno de ellos puede necesitarse varias veces para varios valores de salida.

Dado que sólo puede repetir una vez más de un iterador, product no se puede implementar equivalente a esto:

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

Si aquí b es un iterador, se extingue tras la primera iteración del bucle exterior y ningún se producirán más elementos en ejecuciones posteriores de for y in b.

product trabajos en torno a este problema mediante el almacenamiento de todos los elementos que son producidos por b, para que puedan ser utilizadas en varias ocasiones:

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) 

De hecho, product intentos para almacenar los elementos producidos por todos los iterables se se da, aunque eso podría evitarse para su primer parámetro. La función solo necesita recorrer la primera iterable una vez, por lo que no tendría que almacenar esos valores en caché. Pero intenta hacer de todos modos, lo que lleva al MemoryError que ves.

Answer 2

itertools.product no almacena los productos intermedios en la memoria, pero almacena las versiones tuple de los iteradores originales.

Esto puede verse mirando la fuente del módulo itertools. Está en el archivo Modules/itertoolsmodule.c en la distribución fuente de Python 2.7.2. No encontramos, en la función product_new (básicamente el constructor del objeto product) de la línea 1828 en adelante:

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

En ese código, args son los argumentos a product. En la tercera línea de este fragmento de código, el argumento i th se convierte en una tupla. Por lo tanto, el código intenta convertir su iterador xrange(0, 10**9) en una tupla, lo que da como resultado un MemoryError.

No estoy seguro de por qué itertools.product se comporta así. En lugar de almacenar cada iterador de entrada como una tupla, debería ser suficiente para almacenar el último elemento devuelto por cada iterador. (EDITAR: Véase la respuesta de sth por la razón)

Answer 3

Creo que el problema podría ser que xrange devuelve su propio tipo de objeto especial, que no es un iterable normal.

xrange se implementa de tal manera (como las listas) que puede iterar sobre el objeto muchas veces, mientras que puede iterar sobre un objeto generador normal solo una vez. Entonces, algo de esta funcionalidad es responsable del error de memoria.