¿Por qué sumr en listas es (a veces) más rápido que itertools.chain?

Respondí varias preguntas aquí usando esto para “aplanar” una lista de listas:

>>> l = [[1,2,3],[4,5,6],[7,8,9]] >>> sum(l,[]) 

Funciona bien y rinde:

 [1, 2, 3, 4, 5, 6, 7, 8, 9] 

aunque me dijeron que el operador de sum hace a = a + b que no es tan itertools.chain como itertools.chain

Mi pregunta planeada fue “¿por qué es posible en listas donde se evita en cadenas?”

 import itertools,timeit print(timeit.timeit("sum(l,[])",setup='l = [[1,2,3],[4,5,6],[7,8,9]]')) print(timeit.timeit("list(itertools.chain.from_iterable(l))",setup='l = [[1,2,3],[4,5,6],[7,8,9]]')) 

Lo hice varias veces y siempre obtengo las mismas cifras que a continuación:

 0.7155522836070246 0.9883352857722025 

Para mi sorpresa, la chain – recomendada en sum para las listas por todos en varios comentarios sobre mis respuestas – es mucho más lenta.

Todavía es interesante cuando se itera en un bucle for porque en realidad no crea la lista, pero al crear la lista, la sum gana.

Entonces, ¿debemos eliminar itertools.chain y usar sum cuando el resultado esperado es una list ?

EDITAR: gracias a algunos comentarios, hice otra prueba aumentando el número de listas

 s = 'l = [[4,5,6] for _ in range(20)]' print(timeit.timeit("sum(l,[])",setup=s)) print(timeit.timeit("list(itertools.chain.from_iterable(l))",setup=s)) 

Ahora me sale lo contrario:

 6.479897810702537 3.793455760814343 

Sus entradas de prueba son pequeñas. En esas escalas, el horrible tiempo de ejecución asintótico O (n ^ 2) de la versión de sum no es visible. Los tiempos están dominados por factores constantes, y la sum tiene un factor constante mejor, ya que no tiene que funcionar a través de iteradores.

Con listas más grandes, queda claro que la sum no está diseñada para este tipo de cosas:

 >>> timeit.timeit('list(itertools.chain.from_iterable(l))', ... 'l = [[i] for i in xrange(5000)]; import itertools', ... number=1000) 0.20425895931668947 >>> timeit.timeit('sum(l, [])', 'l = [[i] for i in xrange(5000)]', number=1000) 49.55303902059097 

Para la primera pregunta , “Para mi sorpresa, la cadena – recomendada sobre la sum de las listas por parte de todos en varios comentarios sobre mis respuestas – es mucho más lenta”, hay dos razones por las que observa los tiempos:

  • Para entradas pequeñas, los tiempos están dominados por la sobrecarga de llamadas a funciones. Llamar tanto a la list como a chain.from_iterable es más costoso que llamar solo sum . El trabajo real de concatenar las entradas pequeñas es más rápido que el trabajo para realizar las llamadas de función y método.

  • Para entradas más grandes, el comportamiento cuadrático esperado de la lógica a a = a + b dominará.

Para su otra pregunta , “¿por qué es posible en listas donde se evita en cadenas?”, La respuesta es que no podemos detectar e informar todos los casos cuadráticos, por lo que solo informamos sobre aquel en el que es más probable que tropiece un usuario. accidentalmente.

Además, la ''.join(list_of_strings) de ''.join(list_of_strings) es más difícil de averiguar si aún no lo sabe. En contraste, los arreglos de trabajo para las listas son mucho más fáciles de encontrar, t=[]; for s in list_of_lists: t+=s t=[]; for s in list_of_lists: t+=s .

Usando la alternativa de no-itertools , debería poder obtener un rendimiento razonable con extensiones de lista en el lugar simples:

 result = [] for seq in list_of_lists: result += seq 

El bucle se ejecuta a “velocidad de Python” en lugar de “velocidad de C”, pero no hay una sobrecarga de llamada de función, no hay una capa de iteración adicional y, lo que es más importante, la concatenación de la lista puede aprovechar la longitud conocida de la entrada, por lo que puede pre-asignar el espacio necesario para el resultado (esto se denomina __length_hint__ ).

Otro pensamiento , nunca debes confiar en los tiempos que involucran el crecimiento de las listas de manera incremental. La lógica interna utiliza realloc () para cambiar el tamaño de la lista a medida que crece. En las suites de tiempo, el entorno es favorable y el realloc a menudo puede extenderse en el lugar porque no hay otros datos en el camino. Sin embargo, la misma lógica utilizada en el código real puede funcionar mucho peor porque la memoria más fragmentada hace que realloc tenga que copiar todos los datos a un espacio vacío más grande. En otras palabras, los tiempos pueden no ser en absoluto indicativos del rendimiento real en el código real que le interesa.

En cualquier caso , la razón principal por la que sum () es la forma en que está es porque Guido van Rossum y Alex Martelli pensaron que eso es lo mejor para el idioma: