Concatenación de Python vs velocidad de adición en las listas

Tomando este fragmento de interactivepython.org:

def test1(): # concat l = [] for i in range(1000): l = l + [i] def test2(): # append l = [] for i in range(1000): l.append(i) 

 concat 6.54352807999 milliseconds append 0.306292057037 milliseconds 

Donde el bloque inferior es el tiempo de ejecución.

Dice que la concatenación es O (k), donde k es la “longitud de la lista que se está concatenando”. No estoy seguro de si esto significa la lista que está agregando a (original) o la lista que va a agregar. Pero en estos dos bucles parece que solo estás realizando 1 paso por iteración. Entonces, ¿por qué es mucho más rápido agregar?

Si cambia test1 a:

 def test1(): # concat l = [] for i in range(1000): l += [i] 

los tiempos serán mucho más cercanos y en realidad estás haciendo lo que está haciendo el append no creando una nueva lista cada vez.

 In [26]: %timeit test1() 10000 loops, best of 3: 169 µs per loop In [27]: %timeit test2() 10000 loops, best of 3: 115 µs per loop 

Si coloca print id en su código, verá que en la test1 está creando un nuevo objeto cada vez, pero en la test2 siempre es la misma lista:

 In [41]: test1() 139758194625352 139758206001808 139758205966960 139758194625352 139758206001808 139758205966960 139758194625352 139758206001808 139758205966960 139758194625352 Out[41]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] In [42]: test2() 139758206002600 139758206002600 139758206002600 139758206002600 139758206002600 139758206002600 139758206002600 139758206002600 139758206002600 139758206002600 Out[42]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

Debido a que la concatenación tiene que construir un nuevo objeto de lista en cada iteración:

Crear una nueva lista cada vez es mucho más costoso que agregar un elemento a una lista existente.

Bajo el capó, .append() llenará los índices preasignados en la matriz C, y solo periódicamente el objeto de la lista tiene que boost esa matriz. La construcción de un nuevo objeto de lista, por otro lado, tiene que asignar una matriz C cada vez .