¿Por qué es [] más rápido que list ()?

Recientemente comparé las velocidades de procesamiento de []y me list()sorprendió descubrir que []funciona más de tres veces más rápido que list(). Me encontré con la misma prueba con {}y dict()y los resultados fueron prácticamente idénticos: []y {}ambos tomaron alrededor 0.128sec / millón de ciclos, mientras que list()y dict()tomó aproximadamente 0.428sec / millón de ciclos de cada uno.

¿Por qué es esto? Hacer []y {}(y, probablemente, ()y '', también) inmediatamente pasar de nuevo a copias de alguna vacío stock literal, mientras que sus homólogos explícitamente nombradas-( list(), dict(), tuple(), str()) van totalmente sobre la creación de un objeto, ya sea o no que en realidad tienen elementos?

No tengo idea de cómo difieren estos dos métodos, pero me encantaría descubrirlo. No pude encontrar una respuesta en los documentos o en SO, y la búsqueda de paréntesis vacíos resultó ser más problemático de lo que esperaba.

Obtuve mis resultados de tiempo llamando timeit.timeit("[]")y timeit.timeit("list()"), timeit.timeit("{}")y timeit.timeit("dict()"), para comparar listas y diccionarios, respectivamente. Estoy ejecutando Python 2.7.9.

Recientemente descubrí " ¿Por qué si es Verdadero más lento que si 1? " Que compara el rendimiento de if Trueto if 1y parece tocar un escenario literal versus global similar; quizás valga la pena considerar también.

Porque []y {}son sintaxis literal . Python puede crear bytecode solo para crear la lista o los objetos del diccionario:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list()y dict()son objetos separados. Sus nombres deben resolverse, la pila debe estar involucrada para enviar los argumentos, el marco debe almacenarse para recuperarlo más tarde y debe realizarse una llamada. Todo eso lleva más tiempo.

Para el caso vacío, eso significa que tiene al menos un LOAD_NAME(que tiene que buscar a través del espacio de nombres global, así como el __builtin__módulo ) seguido de un CALL_FUNCTION, que tiene que preservar el marco actual:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

Puede cronometrar la búsqueda de nombres por separado con timeit:

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

La discrepancia de tiempo probablemente es una colisión de hash de diccionario. Resta esos tiempos de los tiempos para llamar a esos objetos, y compara el resultado con los tiempos para usar literales:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

Entonces, tener que llamar al objeto lleva unos 1.00 - 0.31 - 0.30 == 0.39segundos adicionales por cada 10 millones de llamadas.

Puede evitar el costo de búsqueda global aliasing los nombres globales como locales (usando una timeitconfiguración, todo lo que se une a un nombre es un local):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

pero nunca puedes superar ese CALL_FUNCTIONcosto.

list()requiere una búsqueda global y una llamada a función, pero se []compila en una sola instrucción. Ver:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None

Porque listes una función para convertir digamos una cadena en un objeto de lista, mientras que []se usa para crear una lista desde el principio. Pruebe esto (puede tener más sentido para usted):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Mientras

y = ["wham bam"]
>>> y
["wham bam"]

Te da una lista real que contiene todo lo que pones en ella.

Las respuestas aquí son geniales, al punto y cubren completamente esta pregunta. Dejaré un paso más abajo del código de bytes para aquellos interesados. Estoy usando el repositorio más reciente de CPython; las versiones anteriores se comportan de manera similar a este respecto, pero pueden existir ligeros cambios.

Aquí hay un desglose de la ejecución para cada uno de estos, BUILD_LISTpor []y CALL_FUNCTIONpara list().

La BUILD_LISTinstrucción:

Deberías ver el horror:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Terriblemente enrevesada, lo sé. Así de simple es:

• Cree una nueva lista con PyList_New(esto asigna principalmente la memoria para un nuevo objeto de lista), opargseñalando el número de argumentos en la pila. Directo al grano.
• Comprueba que nada salió mal if (list==NULL).
• Agregue cualquier argumento (en nuestro caso, esto no se ejecuta) ubicado en la pila con PyList_SET_ITEM(una macro).

¡No es de extrañar que sea rápido! Está hecho a medida para crear nuevas listas, nada más :-)

La CALL_FUNCTIONinstrucción:

Esto es lo primero que ve cuando mira el manejo del código CALL_FUNCTION:

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Parece bastante inofensivo, ¿verdad? Bueno, no, desafortunadamente no, no call_functiones un tipo directo que llamará a la función de inmediato, no puede. En su lugar, toma el objeto de la pila, toma todos los argumentos de la pila y luego cambia según el tipo de objeto; Es una:

• PyCFunction_Type? No, se trata list, listno es de tipoPyCFunction
• PyMethodType? No, ver anterior.
• PyFunctionType? No, ver anterior.

Estamos llamando al listtipo, el argumento pasado a call_functiones PyList_Type. CPython ahora tiene que llamar a una función genérica para manejar cualquier objeto invocable llamado _PyObject_FastCallKeywords, yay más llamadas a funciones.

Esta función nuevamente realiza algunas comprobaciones para ciertos tipos de funciones (que no puedo entender por qué) y luego, después de crear un dict para kwargs si es necesario , pasa a llamar _PyObject_FastCallDict.

_PyObject_FastCallDictfinalmente nos lleva a alguna parte! Después de realizar incluso más comprobaciones , toma la tp_callranuratype de la typeque hemos pasado, es decir, toma type.tp_call. Luego procede a crear una tupla a partir de los argumentos pasados _PyStack_AsTupley, finalmente, ¡ finalmente se puede hacer una llamada !

tp_call, que coincide type.__call__toma el control y finalmente crea el objeto de lista. Llama a las listas __new__que le corresponden PyType_GenericNewy le asigna memoria PyType_GenericAlloc: Esta es en realidad la parte en la que se pone al día PyList_New, finalmente . Todo lo anterior es necesario para manejar objetos de forma genérica.

Al final, type_callllama list.__init__e inicializa la lista con los argumentos disponibles, luego regresamos por donde vinimos. :-)

Finalmente, recuerda LOAD_NAME, ese es otro tipo que contribuye aquí.

Es fácil ver que, cuando se trata de nuestra entrada, Python generalmente tiene que saltar a través de los aros para descubrir realmente la Cfunción adecuada para hacer el trabajo. No tiene la cortesía de llamarlo de inmediato porque es dinámico, alguien podría enmascarar list( y mucha gente lo hace ) y se debe tomar otro camino.

Aquí es donde list()pierde mucho: la exploración de Python debe hacer para descubrir qué diablos debería hacer.

La sintaxis literal, por otro lado, significa exactamente una cosa; no se puede cambiar y siempre se comporta de manera predeterminada.

^{Nota al pie: Todos los nombres de funciones están sujetos a cambios de una versión a otra. El punto sigue en pie y lo más probable es que permanezca en cualquier versión futura, es la búsqueda dinámica que ralentiza las cosas.}

¿Por qué es []más rápido que list()?

La razón más importante es que Python se trata list()como una función definida por el usuario, lo que significa que puede interceptarla aliasando algo más listy hacer algo diferente (como usar su propia lista subclasificada o tal vez una deque).

Inmediatamente crea una nueva instancia de una lista integrada con [].

Mi explicación busca darte la intuición para esto.

Explicación

[] se conoce comúnmente como sintaxis literal.

En la gramática, esto se conoce como "visualización de lista". De los documentos :

Una visualización de lista es una serie posiblemente vacía de expresiones encerradas entre corchetes:

list_display ::=  "[" [starred_list | comprehension] "]"

Una visualización de lista produce un nuevo objeto de lista, el contenido se especifica mediante una lista de expresiones o una comprensión. Cuando se proporciona una lista de expresiones separadas por comas, sus elementos se evalúan de izquierda a derecha y se colocan en el objeto de la lista en ese orden. Cuando se suministra una comprensión, la lista se construye a partir de los elementos resultantes de la comprensión.

En resumen, esto significa que listse crea un objeto de tipo incorporado .

No hay forma de eludir esto, lo que significa que Python puede hacerlo tan rápido como sea posible.

Por otro lado, list()se puede interceptar creando un generador incorporado listutilizando el constructor de la lista integrada.

Por ejemplo, supongamos que queremos que nuestras listas se creen ruidosamente:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

Luego podríamos interceptar el nombre listen el ámbito global del nivel del módulo, y luego cuando creamos un list, en realidad creamos nuestra lista de subtipos:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

Del mismo modo, podríamos eliminarlo del espacio de nombres global

del list

y ponerlo en el espacio de nombres incorporado:

import builtins
builtins.list = List

Y ahora:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

Y tenga en cuenta que la visualización de la lista crea una lista incondicionalmente:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

Probablemente solo hagamos esto temporalmente, así que deshazcamos nuestros cambios: primero elimine el nuevo Listobjeto de los archivos incorporados:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

Oh, no, perdimos el rastro del original.

No se preocupe, todavía podemos obtenerlo list: es el tipo de una lista literal:

>>> builtins.list = type([])
>>> list()
[]

Entonces...

¿Por qué es []más rápido que list()?

Como hemos visto, podemos sobrescribir list, pero no podemos interceptar la creación del tipo literal. Cuando usamos listtenemos que hacer las búsquedas para ver si hay algo allí.

Luego tenemos que llamar a cualquier llamada que hayamos buscado. De la gramática:

Una llamada llama a un objeto invocable (por ejemplo, una función) con una serie de argumentos posiblemente vacía:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Podemos ver que hace lo mismo con cualquier nombre, no solo con la lista:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Para []no hay llamada de función en el nivel de código de bytes Python:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Simplemente va directamente a la construcción de la lista sin búsquedas ni llamadas a nivel de bytecode.

Conclusión

Hemos demostrado que listpuede ser interceptado con código de usuario utilizando las reglas de alcance, y que list()busca un invocable y luego lo llama.

Mientras que []es una visualización de lista, o un literal, y por lo tanto evita la búsqueda de nombre y la llamada a función.