examples - ¿Hay alguna forma de evitar que Python list.append() se vuelva progresivamente más lento en un bucle a medida que la lista crece?

pop python

Question

Tengo un archivo grande del que estoy leyendo y convierto cada pocas líneas a una instancia de un Objeto.

Como estoy revisando el archivo, guardo la instancia en una lista usando list.append (instance), y luego continúo el bucle.

Este es un archivo que está alrededor de ~100MB por lo que no es demasiado grande, pero a medida que la lista crece, el bucle se ralentiza progresivamente. (Imprimo la hora de cada vuelta en el circuito).

Esto no es intrínseco al bucle ~ cuando imprimo cada nueva instancia mientras recorro el archivo, el programa progresa a velocidad constante ~ solo cuando lo anexo a una lista se vuelve lento.

Mi amigo sugirió desactivar la recolección de basura antes del ciclo while y habilitarlo luego y hacer una llamada a la recolección de basura.

¿Alguien más observó un problema similar con list.append que se vuelve más lento? ¿Hay alguna otra forma de eludir esto?

Voy a probar las siguientes dos cosas que se sugieren a continuación.

(1) "preasignar" la memoria ~ ¿cuál es la mejor manera de hacer esto? (2) Intenta usar deque

Varias publicaciones (vea el comentario de Alex Martelli) sugirieron la fragmentación de la memoria (tiene una gran cantidad de memoria disponible como yo) ~, pero no hay soluciones obvias para el rendimiento de esto.

Para replicar el fenómeno, ejecute el código de prueba proporcionado a continuación en las respuestas y suponga que las listas tienen datos útiles.

gc.disable () y gc.enable () ayudan con el tiempo. También haré un análisis cuidadoso de dónde se gasta todo el tiempo.

Answer 1

¿Puedes intentar http://docs.python.org/release/2.5.2/lib/deque-objects.html asignar la cantidad esperada de elementos necesarios en tu lista? ? Apuesto a que esa lista es un almacenamiento contiguo que debe ser reasignado y copiado cada pocas iteraciones. (similar a algunas implementaciones populares de std :: vector en c ++)

EDIT: respaldado por http://www.python.org/doc/faq/general/#how-are-lists-implemented

Answer 2

Encontré este problema al usar matrices Numpy, creado de la siguiente manera:

import numpy
theArray = array([],dtype=''int32'')

Anexar a esta matriz dentro de un bucle tomó progresivamente más tiempo a medida que crecía la matriz, lo que fue un gran obstáculo ya que tenía 14M que me gustaría hacer.

La solución de recolector de basura descrita anteriormente sonaba prometedor pero no funcionó.

Lo que funcionó fue crear la matriz con un tamaño predefinido de la siguiente manera:

theArray = array(arange(limit),dtype=''int32'')

Solo asegúrate de que el límite sea ​​más grande que la matriz que necesitas.

A continuación, puede establecer cada elemento en la matriz directamente:

theArray[i] = val_i

Y al final, si es necesario, puede eliminar la porción no utilizada de la matriz

theArray = theArray[:i]

Esto hizo una GRAN diferencia en mi caso.

Answer 3

Muchas de estas respuestas son solo suposiciones descabelladas. Me gusta Mike Graham es el mejor porque tiene razón sobre cómo se implementan las listas. Pero he escrito un código para reproducir su reclamo y analizarlo más a fondo. Aquí hay algunos hallazgos.

Aquí es con lo que comencé.

import time
x = []
for i in range(100):
    start = time.clock()
    for j in range(100000):
        x.append([])
    end = time.clock()
    print end - start

Solo estoy agregando listas vacías a la lista x . Imprimo una duración por cada 100.000 anexos, 100 veces. Se ralentiza como dijiste. (0.03 segundos para la primera iteración, y 0.84 segundos para la última ... una gran diferencia).

Obviamente, si instancia una lista pero no la agrega a x , se ejecuta mucho más rápido y no aumenta con el tiempo.

Pero si cambia x.append([]) a x.append(''hello world'') , no hay aumento de velocidad. El mismo objeto se está agregando a la lista 100 * 100,000 veces.

Lo que hago de esto:

• La disminución de velocidad no tiene nada que ver con el tamaño de la lista. Tiene que ver con la cantidad de objetos en vivo de Python.
• Si no agrega los elementos a la lista, solo obtienen basura recolectada de inmediato y ya no están siendo administrados por Python.
• Si agrega el mismo elemento una y otra vez, la cantidad de objetos de Python activos no aumenta. Pero la lista tiene que redimensionarse de vez en cuando. Pero esta no es la fuente del problema de rendimiento.
• Como está creando y agregando muchos objetos nuevos a una lista, estos permanecen en vivo y no son basura. La ralentización probablemente tiene algo que ver con esto.

En cuanto a los aspectos internos de Python que podrían explicar esto, no estoy seguro. Pero estoy bastante seguro de que la estructura de datos de la lista no es la culpable.

Answer 4

No hay nada que eludir: agregar a una lista es O (1) amortizado.

Una lista (en CPython) es una matriz al menos tan larga como la lista y hasta dos veces más larga. Si la matriz no está llena, agregarla a una lista es tan simple como asignar uno de los miembros de la matriz (O (1)). Cada vez que la matriz está llena, se duplica automáticamente el tamaño. Esto significa que, en ocasiones, se requiere una operación O (n), pero solo se requiere cada n operaciones , y cada vez se requiere menos, ya que la lista se agranda. O (n) / n ==> O (1). (En otras implementaciones, los nombres y detalles podrían cambiar potencialmente, pero al mismo tiempo las propiedades se mantendrán).

Agregar a una lista ya escala.

¿Es posible que cuando el archivo llegue a ser grande no puedas guardar todo en la memoria y tengas problemas con el sistema operativo de paginación en el disco? ¿Es posible que sea una parte diferente de tu algoritmo que no se escale bien?

Answer 5

Use un conjunto en su lugar y luego conviértalo en una lista al final

my_set=set()
with open(in_file) as f:
    # do your thing
    my_set.add(instance)


my_list=list(my_set)
my_list.sort() # if you want it sorted

Tuve el mismo problema y esto resolvió el problema del tiempo por varias órdenes.

Answer 6

El rendimiento deficiente que observa es causado por un error en el recolector de basura de Python en la versión que está utilizando. Actualice a Python 2.7, o 3.1 o superior para recuperar el comportamiento 0 (1) amorizado esperado de la lista que se agrega en Python.

Si no puede actualizar, deshabilite la recolección de elementos no utilizados a medida que crea la lista y actívela después de terminar.

(También puede ajustar los desencadenantes del recolector de elementos no utilizados o llamar selectivamente a medida que avanza, pero no exploro estas opciones en esta respuesta porque son más complejos y sospecho que su caso de uso es susceptible a la solución anterior).

Fondo:

Ver: https://bugs.python.org/issue4074 y también https://docs.python.org/release/2.5.2/lib/module-gc.html

El periodista observa que la adición de objetos complejos (objetos que no son números o cadenas) a una lista se ralentiza linealmente a medida que la lista crece en longitud.

La razón de este comportamiento es que el recolector de elementos no utilizados está comprobando y volviendo a revisar cada objeto de la lista para ver si son aptos para la recolección de elementos no utilizados. Este comportamiento provoca el aumento lineal en el tiempo para agregar objetos a una lista. Se espera que una solución llegue a py3k, por lo que no debe aplicarse al intérprete que está utilizando.

Prueba:

Ejecuté una prueba para demostrar esto. Para las iteraciones de 1k anexo 10k objetos a una lista, y registro el tiempo de ejecución para cada iteración. La diferencia general de tiempo de ejecución es inmediatamente obvia. Con la recolección de basura desactivada durante el ciclo interno de la prueba, el tiempo de ejecución en mi sistema es de 18.6 segundos. Con la recolección de basura habilitada para toda la prueba, el tiempo de ejecución es 899.4s.

Esta es la prueba:

import time
import gc

class A:
    def __init__(self):
        self.x = 1
        self.y = 2
        self.why = ''no reason''

def time_to_append(size, append_list, item_gen):
    t0 = time.time()
    for i in xrange(0, size):
        append_list.append(item_gen())
    return time.time() - t0

def test():
    x = []
    count = 10000
    for i in xrange(0,1000):
        print len(x), time_to_append(count, x, lambda: A())

def test_nogc():
    x = []
    count = 10000
    for i in xrange(0,1000):
        gc.disable()
        print len(x), time_to_append(count, x, lambda: A())
        gc.enable()

Fuente completa: https://hypervolu.me/~erik/programming/python_lists/listtest.py.txt

Resultado gráfico: el rojo está con gc on, blue está con gc off. El eje y tiene segundos escalados logarítmicamente.

http://hypervolu.me/~erik/programming/python_lists/gc.png

Como las dos tramas difieren en varios órdenes de magnitud en el componente y, aquí están independientemente con el eje y escalado linealmente.

http://hypervolu.me/~erik/programming/python_lists/gc_on.png

http://hypervolu.me/~erik/programming/python_lists/gc_off.png

Curiosamente, con la recolección de basura desactivada, solo vemos pequeños picos en el tiempo de ejecución por 10k, lo que sugiere que los costos de reasignación de la lista de Python son relativamente bajos. En cualquier caso, son muchos órdenes de magnitud inferiores a los costos de recolección de basura.

La densidad de los gráficos anteriores hace que sea difícil ver que con el recolector de basura activado, la mayoría de los intervalos tienen un buen rendimiento; es solo cuando el recolector de basura hace un ciclo que encontramos el comportamiento patológico. Puede observar esto en este histograma de 10k de tiempo de agregado. La mayoría de los puntos de datos caen alrededor de 0.02s por cada 10k.

http://hypervolu.me/~erik/programming/python_lists/gc_on.hist.png

Los datos brutos utilizados para producir estos gráficos se pueden encontrar en http://hypervolu.me/~erik/programming/python_lists/