remove - python list functions

¿Por qué la asignación de sectores es más rápida que `list.insert`?

Question

Inspirado por esta buena respuesta ,

Aquí hay un punto de referencia:

import timeit

def test1():
    a = [1,2,3]
    a.insert(0,1)

def test2():
    a = [1,2,3]
    a[0:0]=[1]

print (timeit.timeit(''test1()'',''from __main__ import test1''))
print (timeit.timeit(''test2()'',''from __main__ import test2''))

Para mí, test2 es un poco más rápido (~ 10%). ¿Por qué es ese el caso? Espero que sea más lento ya que:

1. la asignación de segmentos debe poder aceptar iterables de cualquier longitud y, por lo tanto, debe ser más general.
2. En la asignación de segmentos, necesitamos crear una nueva lista en el lado derecho solo para que funcione.

¿Alguien puede ayudarme a entender esto?

(usando python 2.7 en OS-X 10.5.8)

Answer 1

Su primer caso de prueba debe llamar al método insert en la lista a , mientras que todas las operaciones en test2 se manejan directamente en código de byte. Tenga en cuenta el CALL_FUNCTION en el desmontaje de la test1 continuación. Llamar a las funciones es moderadamente caro en Python: ciertamente lo suficientemente caro para dar cuenta de una diferencia de unos pocos por ciento en el tiempo de ejecución.

>>> import dis
>>> dis.dis(test1)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_FAST                0 (a)
             18 LOAD_ATTR                0 (insert)
             21 LOAD_CONST               4 (0)
             24 LOAD_CONST               1 (1)
             27 CALL_FUNCTION            2
             30 POP_TOP             
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE        
>>> dis.dis(test2)
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (2)
              6 LOAD_CONST               3 (3)
              9 BUILD_LIST               3
             12 STORE_FAST               0 (a)

  3          15 LOAD_CONST               1 (1)
             18 BUILD_LIST               1
             21 LOAD_FAST                0 (a)
             24 LOAD_CONST               4 (0)
             27 LOAD_CONST               4 (0)
             30 STORE_SLICE+3       
             31 LOAD_CONST               0 (None)
             34 RETURN_VALUE        

Mala explicacion

Publiqué esto primero, pero después de considerarlo creo que no es correcto. La diferencia que describo aquí solo debe hacer una diferencia notable cuando hay muchos datos que se deben mover, lo cual no es el caso en la prueba aquí. E incluso con una gran cantidad de datos, la diferencia es solo un par de porcentajes:

import timeit

def test1():
    a = range(10000000)
    a.insert(1,1)

def test2():
    a = range(10000000)
    a[1:1]=[1]

>>> timeit.timeit(test1, number=10)
6.008707046508789
>>> timeit.timeit(test2, number=10)
5.861173868179321

El método list.insert es implementado por la función ins1 en listobject.c . Verás que copia las referencias de los elementos para la cola de la lista una por una:

for (i = n; --i >= where; )
    items[i+1] = items[i];

Por otro lado, la asignación de segmentos se implementa mediante la función list_ass_slice , que llama a memmove :

memmove(&item[ihigh+d], &item[ihigh],
        (k - ihigh)*sizeof(PyObject *));

Entonces, creo que la respuesta a su pregunta es que la función de la biblioteca de C memmove está mejor optimizada que el simple bucle. Vea aquí para la implementación de memmove glibc : Creo que cuando se llama desde list_ass_slice , finalmente termina llamando a _wordcopy_bwd_aligned que puede ver que está muy optimizado a mano.