¿Por qué una expresión generadora necesita mucha memoria?

Problema

Supongamos que quiero encontrar n**2 para todos los números menores que 20000000.

Configuración general para las tres variantes que pruebo:

import time, psutil, gc

gc.collect()
mem_before = psutil.virtual_memory()[3]
time1 = time.time()

# (comprehension, generator, function)-code comes here

time2 = time.time()
mem_after =  psutil.virtual_memory()[3]

print "Used Mem = ", (mem_after - mem_before)/(1024**2)  # convert Byte to Megabyte
print "Calculation time = ", time2 - time1

Tres opciones para calcular estos números:

1. Crear una lista de vía comprensión: 

x = [i**2 for i in range(20000000)]

Es realmente lento y consume mucho tiempo:

Used Mem =  1270  # Megabytes
Calculation time =  33.9309999943  # Seconds

2. Crear un generador usando '()':

x = (i**2 for i in range(20000000))

Es mucho más rápido que la opción 1, pero todavía usa mucho de memoria:

Used Mem =  611 
Calculation time =  0.278000116348

3. Definición de una función generadora (más eficiente):

def f(n):
    i = 0
    while i < n:
        yield i**2
        i += 1
x = f(20000000)

Su consumo: 

Used Mem =  0
Calculation time =  0.0

Las preguntas son:

  1. ¿Cuál es la diferencia entre la primera y la segunda solución? Usando () crea un generador, entonces, ¿por qué necesita mucha memoria?
  2. ¿Hay alguna función incorporada equivalente a mi tercera opción?
Author: Azat Ibrakov, 2016-05-11
Source

2 answers

  1. Como otros han señalado en los comentarios, range crea un list en Python 2. Por lo tanto, no es el generador per se el que usa la memoria, sino el range que usa el generador:

    x = (i**2 for i in range(20000000))  
# builds a 2*10**7 element list, not for the squares , but for the bases

>>> sys.getsizeof(range(100))
872
>>> sys.getsizeof(xrange(100))
40
>>> sys.getsizeof(range(1000))
8720
>>> sys.getsizeof(xrange(1000))
40
>>> sys.getsizeof(range(20000000))
160000072
>>> sys.getsizeof(xrange(20000000))
40

    Esto también explica por qué su segunda versión (la expresión generadora) usa alrededor de la mitad de la memoria de la primera versión (la comprensión de la lista) ya que la primera construye dos listas (para las bases y los cuadrados) mientras que la segunda solo construye una lista para el base.

  2. xrange(20000000) por lo tanto, mejora en gran medida el uso de la memoria, ya que devuelve un iterable perezoso. Esta es esencialmente la forma eficiente de memoria incorporada para iterar sobre un rango de números que refleja su tercera versión (con la flexibilidad adicional de start, stop y step):

    x = (i**2 for i in xrange(20000000))

    En Python 3, range es esencialmente lo que xrange solía ser en Python 2. Sin embargo, el objeto Python 3 range tiene algunas características agradables que Python 2 xrange no tiene, como O(1) cortar, contiene, etc.

Algunas referencias:

 52
Author: schwobaseggl,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-05-11 17:25:04

1.- El objeto debe ser creado en memoria, por lo que en su segunda solución , el generador es creado pero no computado , pero todavía tiene memoria, python probablemente reserve algo de memoria para que su cálculo sea eficiente, no sabemos sobre el intérprete magic, también observe que range funtion crea la lista completa de 0 a 200000, por lo que de hecho todavía está construyendo esa lista en memoria.

2.- Puedes usar itertool.imap : 

squares = itertools.imap(lambda x: x**2, xrange(200000))
 1
Author: Netwave,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-05-11 08:20:13