Maneras eficientes de duplicar la matriz / lista en Python

Nota: soy un desarrollador de Ruby que trata de encontrar mi camino en Python.

Cuando quise averiguar por qué algunos scripts usan mylist[:] lugar de list(mylist) para duplicar listas, hice un rápido punto de referencia de los diversos métodos para duplicar el range(10) (vea el código a continuación).

EDITAR: timeit las pruebas para usar Python’s timeit como se sugiere a continuación. Esto hace que sea imposible compararlo directamente con Ruby, porque timeit no tiene en cuenta el bucle mientras que Ruby’s Benchmark sí lo hace, por lo que el código de Ruby es solo para referencia .

Python 2.7.2

 Array duplicating. Tests run 50000000 times list(a) 18.7599430084 copy(a) 59.1787488461 a[:] 9.58828091621 a[0:len(a)] 14.9832749367 

Para referencia, escribí el mismo script en Ruby también:

Ruby 1.9.2p0

 Array duplicating. Tests 50000000 times user system total real Array.new(a) 14.590000 0.030000 14.620000 ( 14.693033) Array[*a] 18.840000 0.060000 18.900000 ( 19.156352) a.take(a.size) 8.780000 0.020000 8.800000 ( 8.805700) a.clone 16.310000 0.040000 16.350000 ( 16.384711) a[0,a.size] 8.950000 0.020000 8.970000 ( 8.990514) 

Pregunta 1: ¿qué hace mylist[:] diferente que es un 25% más rápido que incluso mylist[0:len(mylist)] ? ¿Se copia directamente en la memoria o qué?

Pregunta 2: edición: los puntos de referencia actualizados ya no muestran grandes diferencias en Python y Ruby. fue: ¿Implementé las pruebas de una manera obviamente ineficiente, de modo que el código Ruby sea mucho más rápido que Python?

Ahora los listados de código:

Pitón:

 import timeit COUNT = 50000000 print "Array duplicating. Tests run", COUNT, "times" setup = 'a = range(10); import copy' print "list(a)\t\t", timeit.timeit(stmt='list(a)', setup=setup, number=COUNT) print "copy(a)\t\t", timeit.timeit(stmt='copy.copy(a)', setup=setup, number=COUNT) print "a[:]\t\t", timeit.timeit(stmt='a[:]', setup=setup, number=COUNT) print "a[0:len(a)]\t", timeit.timeit(stmt='a[0:len(a)]', setup=setup, number=COUNT) 

Rubí:

 require 'benchmark' a = (0...10).to_a COUNT = 50_000_000 puts "Array duplicating. Tests #{COUNT} times" Benchmark.bm(16) do |x| x.report("Array.new(a)") {COUNT.times{ Array.new(a) }} x.report("Array[*a]") {COUNT.times{ Array[*a] }} x.report("a.take(a.size)") {COUNT.times{ a.take(a.size) }} x.report("a.clone") {COUNT.times{ a.clone }} x.report("a[0,a.size]"){COUNT.times{ a[0,a.size] }} end 

Usa el módulo de timeit en python para probar los tiempos.

 from copy import * a=range(1000) def cop(): b=copy(a) def func1(): b=list(a) def slice(): b=a[:] def slice_len(): b=a[0:len(a)] if __name__=="__main__": import timeit print "copy(a)",timeit.timeit("cop()", setup="from __main__ import cop") print "list(a)",timeit.timeit("func1()", setup="from __main__ import func1") print "a[:]",timeit.timeit("slice()", setup="from __main__ import slice") print "a[0:len(a)]",timeit.timeit("slice_len()", setup="from __main__ import slice_len") 

Resultados:

 copy(a) 3.98940896988 list(a) 2.54542589188 a[:] 1.96630120277 #winner a[0:len(a)] 10.5431251526 

Seguramente, los pasos adicionales involucrados en a[0:len(a)] son la razón de su lentitud.

Aquí está la comparación del código de bytes de los dos:

 In [19]: dis.dis(func1) 2 0 LOAD_GLOBAL 0 (range) 3 LOAD_CONST 1 (100000) 6 CALL_FUNCTION 1 9 STORE_FAST 0 (a) 3 12 LOAD_FAST 0 (a) 15 SLICE+0 16 STORE_FAST 1 (b) 19 LOAD_CONST 0 (None) 22 RETURN_VALUE In [20]: dis.dis(func2) 2 0 LOAD_GLOBAL 0 (range) 3 LOAD_CONST 1 (100000) 6 CALL_FUNCTION 1 9 STORE_FAST 0 (a) 3 12 LOAD_FAST 0 (a) #same up to here 15 LOAD_CONST 2 (0) #loads 0 18 LOAD_GLOBAL 1 (len) # loads the builtin len(), # so it might take some lookup time 21 LOAD_FAST 0 (a) 24 CALL_FUNCTION 1 27 SLICE+3 28 STORE_FAST 1 (b) 31 LOAD_CONST 0 (None) 34 RETURN_VALUE 

No puedo comentar sobre el tiempo de Ruby frente al tiempo de python. Pero puedo comentar en la list contra la slice . Aquí hay una inspección rápida del código de bytes:

 >>> import dis >>> a = range(10) >>> def func(a): ... return a[:] ... >>> def func2(a): ... return list(a) ... >>> dis.dis(func) 2 0 LOAD_FAST 0 (a) 3 SLICE+0 4 RETURN_VALUE >>> dis.dis(func2) 2 0 LOAD_GLOBAL 0 (list) 3 LOAD_FAST 0 (a) 6 CALL_FUNCTION 1 9 RETURN_VALUE 

Observe que la list requiere un LOAD_GLOBAL para encontrar la list funciones. La búsqueda de elementos globales (y funciones de llamada) en python es relativamente lenta. Esto explicaría por qué a[0:len(a)] también es más lento. También recuerde que la list debe ser capaz de manejar iteradores arbitrarios, mientras que la división no lo hace. Esto significa que la list debe asignar una nueva lista, empaquetar elementos en esa lista a medida que se repite en la lista y cambiar de tamaño cuando sea necesario. Hay algunas cosas aquí que son caras: cambiar el tamaño si es necesario e iterar (efectivamente en python, no en C). Con el método de corte, puede calcular el tamaño de la memoria que necesitará, así que probablemente pueda evitar el cambio de tamaño, y la iteración se puede hacer completamente en C (probablemente con un memcpy o algo así).

descargo de responsabilidad : no soy un desarrollador de Python, por lo que no sé cómo se implementan con seguridad los elementos internos de list() . Solo estoy especulando en base a lo que sé de la especificación.

EDITAR – Así que he mirado la fuente (con un poco de orientación de Martijn). El código relevante está en listobject.c . list llamadas list_init que luego llama listextend en la línea 799. Esa función tiene algunas verificaciones para ver si puede usar una twig rápida si el objeto es una lista o una tupla (línea 812). Finalmente, el trabajo pesado se realiza a partir de la línea 834:

  src = PySequence_Fast_ITEMS(b); dest = self->ob_item + m; for (i = 0; i < n; i++) { PyObject *o = src[i]; Py_INCREF(o); dest[i] = o; } 

Compare eso con la versión de list_subscript que creo que está definida en list_subscript (línea 2544). Eso llama a list_slice (línea 2570) donde el trabajo pesado se realiza mediante el siguiente bucle (línea 486):

  src = a->ob_item + ilow; dest = np->ob_item; for (i = 0; i < len; i++) { PyObject *v = src[i]; Py_INCREF(v); dest[i] = v; } 

Son prácticamente el mismo código, por lo que no es sorprendente que el rendimiento sea casi el mismo para las listas grandes (donde la sobrecarga de las cosas pequeñas como desempaquetar trozos, buscar variables globales, etc. se vuelve menos importante)


Así es como ejecutaría las pruebas de Python (y los resultados para mi sistema Ubuntu):

 $ python -m timeit -s 'a=range(30)' 'list(a)' 1000000 loops, best of 3: 0.39 usec per loop $ python -m timeit -s 'a=range(30)' 'a[:]' 10000000 loops, best of 3: 0.183 usec per loop $ python -m timeit -s 'a=range(30)' 'a[0:len(a)]' 1000000 loops, best of 3: 0.254 usec per loop