una - ¿Por qué la tupla es más rápida que la lista en Python?

llenar una lista en python (7)

Acabo de leer en "Dive into Python" que "las tuplas son más rápidas que las listas".

Tuple es inmutable y la lista es mutable, pero no entiendo bien por qué tuple es más rápido.

¿Alguien hizo una prueba de rendimiento en esto?

Resumen ejecutivo

Las tuplas tienden a funcionar mejor que las listas en casi todas las categorías:

1) Las tuplas se pueden plegar constantemente .

2) Las tuplas se pueden reutilizar en lugar de copiar.

3) Las tuplas son compactas y no se sobre-asignan.

4) Las tuplas hacen referencia directa a sus elementos.

Las tuplas se pueden plegar constantemente

Las tuplas de constantes pueden precomputarse con el optimizador de mirilla de Python o el optimizador de AST. Las listas, por otro lado, se construyen desde cero:

>>> from dis import dis >>> dis(compile("(10, ''abc'')", '''', ''eval'')) 1 0 LOAD_CONST 2 ((10, ''abc'')) 3 RETURN_VALUE >>> dis(compile("[10, ''abc'']", '''', ''eval'')) 1 0 LOAD_CONST 0 (10) 3 LOAD_CONST 1 (''abc'') 6 BUILD_LIST 2 9 RETURN_VALUE

Las tuplas no necesitan ser copiadas

La ejecución de la tuple(some_tuple) devuelve inmediatamente sí mismo. Dado que las tuplas son inmutables, no es necesario copiarlas:

>>> a = (10, 20, 30) >>> b = tuple(a) >>> a is b True

En contraste, list(some_list) requiere que todos los datos se copien a una nueva lista:

>>> a = [10, 20, 30] >>> b = list(a) >>> a is b False

Las tuplas no se sobre-asignan

Dado que el tamaño de una tupla es fijo, puede almacenarse de manera más compacta que las listas que necesitan una asignación excesiva para que las operaciones de adición () sean eficientes.

Esto le da a las tuplas una buena ventaja de espacio:

>>> import sys >>> sys.getsizeof(tuple(iter(range(10)))) 128 >>> sys.getsizeof(list(iter(range(10)))) 200

Aquí está el comentario de Objects / listobject.c que explica qué están haciendo las listas:

/* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... * Note: new_allocated won''t overflow because the largest possible value * is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t. */

Las tuplas se refieren directamente a sus elementos.

Las referencias a los objetos se incorporan directamente en un objeto de tupla. En contraste, las listas tienen una capa adicional de direccionamiento indirecto a una matriz externa de punteros.

Esto le da a las tuplas una pequeña ventaja de velocidad para búsquedas indexadas y desempaquetado:

$ python3.6 -m timeit -s ''a = (10, 20, 30)'' ''a[1]'' 10000000 loops, best of 3: 0.0304 usec per loop $ python3.6 -m timeit -s ''a = [10, 20, 30]'' ''a[1]'' 10000000 loops, best of 3: 0.0309 usec per loop $ python3.6 -m timeit -s ''a = (10, 20, 30)'' ''x, y, z = a'' 10000000 loops, best of 3: 0.0249 usec per loop $ python3.6 -m timeit -s ''a = [10, 20, 30]'' ''x, y, z = a'' 10000000 loops, best of 3: 0.0251 usec per loop

Así es como se almacena la tupla (10, 20) :

typedef struct { Py_ssize_t ob_refcnt; struct _typeobject *ob_type; Py_ssize_t ob_size; PyObject *ob_item[2]; /* store a pointer to 10 and a pointer to 20 */ } PyTupleObject;

Here es cómo se almacena la lista [10, 20] :

PyObject arr[2]; /* store a pointer to 10 and a pointer to 20 */ typedef struct { Py_ssize_t ob_refcnt; struct _typeobject *ob_type; Py_ssize_t ob_size; PyObject **ob_item = arr; /* store a pointer to the two-pointer array */ Py_ssize_t allocated; } PyListObject;

Tenga en cuenta que el objeto de la tupla incorpora los dos punteros de datos directamente, mientras que el objeto de lista tiene una capa adicional de direccionamiento indirecto a una matriz externa que contiene los dos punteros de datos.

Alex dio una gran respuesta, pero voy a tratar de ampliar algunas cosas que creo que vale la pena mencionar. Las diferencias de rendimiento son generalmente pequeñas y específicas de la implementación: así que no apueste la granja a ellas.

En CPython, las tuplas se almacenan en un solo bloque de memoria, por lo que crear una nueva tupla implica, en el peor de los casos, una sola llamada para asignar memoria. Las listas se asignan en dos bloques: el fijo con toda la información del objeto de Python y un bloque de tamaño variable para los datos. Eso es parte de la razón por la que crear una tupla es más rápido, pero probablemente también explica la leve diferencia en la velocidad de indexación, ya que hay un puntero menos que seguir.

También hay optimizaciones en CPython para reducir las asignaciones de memoria: los objetos de lista desasignados se guardan en una lista libre para que puedan reutilizarse, pero la asignación de una lista no vacía todavía requiere una asignación de memoria para los datos. Las tuplas se guardan en 20 listas gratuitas para tuplas de diferentes tamaños, por lo que la asignación de una tupla pequeña a menudo no requerirá ninguna llamada de asignación de memoria.

Las optimizaciones como esta son útiles en la práctica, pero también pueden hacer que sea muy peligroso depender demasiado de los resultados de ''timeit'' y, por supuesto, son completamente diferentes si te mueves a algo como IronPython, donde la asignación de memoria funciona de manera muy diferente.

Con el poder del módulo timeit , a menudo puede resolver usted mismo las preguntas relacionadas con el rendimiento:

$ python2.6 -mtimeit -s ''a = tuple(range(10000))'' ''for i in a: pass'' 10000 loops, best of 3: 189 usec per loop $ python2.6 -mtimeit -s ''a = list(range(10000))'' ''for i in a: pass'' 10000 loops, best of 3: 191 usec per loop

Esto muestra que la tupla es despreciablemente más rápida que la lista para la iteración. Obtengo resultados similares para la indexación, pero para la construcción, la tupla destruye la lista:

$ python2.6 -mtimeit ''(1, 2, 3, 4)'' 10000000 loops, best of 3: 0.0266 usec per loop $ python2.6 -mtimeit ''[1, 2, 3, 4]'' 10000000 loops, best of 3: 0.163 usec per loop

Entonces, si la velocidad de iteración o la indexación son los únicos factores, efectivamente no hay diferencia, pero para la construcción, las tuplas ganan.

Esencialmente porque la inmutabilidad de la tupla significa que el intérprete puede usar una estructura de datos más ágil y rápida para ella, en comparación con la lista.

La relación de "velocidad de construcción" informada solo es válida para tuplas constantes (aquellas cuyos elementos se expresan mediante literales). Observe atentamente (y repita en su máquina - ¡solo necesita escribir los comandos en una ventana de shell / comando!) ...:

$ python3.1 -mtimeit -s''x,y,z=1,2,3'' ''[x,y,z]'' 1000000 loops, best of 3: 0.379 usec per loop $ python3.1 -mtimeit ''[1,2,3]'' 1000000 loops, best of 3: 0.413 usec per loop $ python3.1 -mtimeit -s''x,y,z=1,2,3'' ''(x,y,z)'' 10000000 loops, best of 3: 0.174 usec per loop $ python3.1 -mtimeit ''(1,2,3)'' 10000000 loops, best of 3: 0.0602 usec per loop $ python2.6 -mtimeit -s''x,y,z=1,2,3'' ''[x,y,z]'' 1000000 loops, best of 3: 0.352 usec per loop $ python2.6 -mtimeit ''[1,2,3]'' 1000000 loops, best of 3: 0.358 usec per loop $ python2.6 -mtimeit -s''x,y,z=1,2,3'' ''(x,y,z)'' 10000000 loops, best of 3: 0.157 usec per loop $ python2.6 -mtimeit ''(1,2,3)'' 10000000 loops, best of 3: 0.0527 usec per loop

No hice las mediciones en la versión 3.0 porque, por supuesto, no la tengo, está totalmente obsoleta y no hay ninguna razón para mantenerla, ya que la 3.1 es superior en todos los aspectos (Python 2.7, si puede actualizarlo, las medidas son casi un 20% más rápidas que 2.6 en cada tarea, y 2.6, como puede ver, es más rápido que 3.1 - así que, si te importa el rendimiento, Python 2.7 es realmente la única versión que debes ir por!).

De todos modos, el punto clave aquí es que, en cada versión de Python, construir una lista a partir de literales constantes es aproximadamente la misma velocidad, o un poco más lento, que construirla con valores a los que hacen referencia las variables; pero las tuplas se comportan de manera muy diferente: ¡construir una tupla a partir de literales constantes suele ser tres veces más rápido que construirla a partir de valores referenciados por variables! Usted puede preguntarse cómo puede ser esto, ¿verdad? -)

Respuesta: el compilador de Python puede identificar fácilmente una tupla hecha de literales constantes como si fuera uno mismo, literal constante e inmutable en sí misma: por lo tanto, esencialmente se construye solo una vez, cuando el compilador convierte la fuente en códigos de bytes y se guarda en la tabla de constantes. "de la función o módulo relevante. Cuando esos bytecodes se ejecutan, solo necesitan recuperar la tupla constante pre-construida - hey presto! -)

Esta fácil optimización no se puede aplicar a las listas, porque una lista es un objeto mutable, por lo que es crucial que, si la misma expresión como [1, 2, 3] ejecuta dos veces (en un bucle, el módulo timeit hace el bucle En su nombre ;-), cada vez se construye un nuevo objeto en la lista, y esa construcción (como la construcción de una tupla cuando el compilador no puede identificarlo trivialmente como un objeto constante e inmutable en tiempo de compilación) toma un poco de tiempo. .

Dicho esto, la construcción de la tupla (cuando ambas construcciones tienen que ocurrir) todavía es casi el doble de rápida que la construcción de la lista, y esa discrepancia puede explicarse por la simple simplicidad de la tupla, que otras respuestas han mencionado repetidamente. Pero, esa simplicidad no tiene en cuenta una aceleración de seis veces o más, ¡como puede observar si solo compara la construcción de listas y tuplas con literales constantes simples como sus elementos! _)

Las tuplas son identificadas por el compilador de Python como una constante inmutable, por lo que el compilador creó solo una entrada en la tabla hash y nunca cambió

Las listas son objetos mutables. Por lo tanto, el compilador actualiza la entrada cuando actualizamos la lista para que sea un poco más lenta en comparación con la tupla.

Un área donde una lista es notablemente más rápida es la construcción a partir de un generador, y en particular, las comprensiones de listas son mucho más rápidas que el equivalente más cercano de la tupla, tuple() con un argumento del generador:

$ python --version Python 3.6.0rc2 $ python -m timeit ''tuple(x * 2 for x in range(10))'' 1000000 loops, best of 3: 1.34 usec per loop $ python -m timeit ''list(x * 2 for x in range(10))'' 1000000 loops, best of 3: 1.41 usec per loop $ python -m timeit ''[x * 2 for x in range(10)]'' 1000000 loops, best of 3: 0.864 usec per loop

Tenga en cuenta, en particular, que la tuple(generator) parece ser un poquito más rápida que la list(generator) , pero [elem for elem in generator] es mucho más rápido que ambos.