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

Recientemente comparé las velocidades de procesamiento de [] y list() y me sorprendió descubrir que [] ejecuta más de tres veces más rápido que list() . Corrí la misma prueba con {} y dict() y los resultados fueron prácticamente idénticos: [] y {} tomaron alrededor de 0,128 segundos / millón de ciclos, mientras que list() y dict() tomaron aproximadamente 0,428 segundos / millón de ciclos cada uno.

¿Por qué es esto? Do [] y {} (y probablemente () y '' , también) devuelvan inmediatamente las copias de algún literal de stock vacío mientras que sus contrapartes explícitamente nombradas ( list() , dict() , tuple() , str() ) ¿Desea crear un objeto en su totalidad, tenga o no elementos?

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

timeit.timeit("[]") resultados de los tiempos llamando a timeit.timeit("[]") y timeit.timeit("list()") , y timeit.timeit("{}") y timeit.timeit("dict()") , Para comparar listas y diccionarios, respectivamente. Estoy corriendo Python 2.7.9.

Recientemente descubrí ” ¿Por qué es más lento que si 1? “, Que compara el rendimiento de if True con if 1 y parece tocar un escenario similar de literal contra global; Quizás también vale la pena considerarlo.

Porque [] y {} son syntax literal . Python puede crear un código de bytes 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 stack debe involucrarse para empujar los argumentos, el marco debe almacenarse para recuperarse más tarde y debe realizarse una llamada. Todo eso lleva más tiempo.

Para el caso vacío, eso significa que tienes al menos un LOAD_NAME (que tiene que buscar a través del espacio de nombres global así como el módulo __builtin__ ) 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 timeit 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 allí es probablemente una colisión hash 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 

Por lo tanto, tener que llamar al objeto requiere un adicional de 1.00 - 0.31 - 0.30 == 0.39 segundos por cada 10 millones de llamadas.

Puede evitar el costo de la búsqueda global al aliasar los nombres globales como locales (utilizando una configuración de timeit , todo lo que vincule 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 se puede superar ese costo CALL_FUNCTION .

list() requiere una búsqueda global y una llamada a función, pero [] comstack 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 

Debido a que list es una función para convertir, digamos, una cadena a un objeto de lista, mientras que [] se usa para crear una lista desde el principio. Prueba esto (podría tener más sentido para ti):

 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 excelentes, hasta el punto y cubren completamente esta pregunta. Bajaré un paso más del código de bytes para los interesados. Estoy usando el repo más reciente de CPython; Las versiones anteriores se comportan de manera similar en este aspecto, pero podrían haber pequeños cambios.

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


La instrucción BUILD_LIST :

Solo 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 complicada, lo sé. Así de simple es:

  • Cree una nueva lista con PyList_New (esto asigna principalmente la memoria para un nuevo objeto de lista), oparg señala el número de argumentos en la stack. Directo al grano.
  • Compruebe que no haya pasado nada con if (list==NULL) .
  • Agregue cualquier argumento (en nuestro caso, esto no se ejecuta) ubicado en la stack 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 instrucción CALL_FUNCTION :

Esto es lo primero que ve cuando mira el código que maneja 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, call_function no es un tipo directo que llamará a la función inmediatamente, no puede. En su lugar, toma el objeto de la stack, toma todos los argumentos de la stack y luego cambia según el tipo de objeto; Es una:

  • PyCFunction_Type ? No, es list , list no es de tipo PyCFunction
  • PyMethodType ? No, ver anterior.
  • PyFunctionType ? Nopee, ver anterior.

Estamos llamando al tipo de list , el argumento que se pasa a call_function es PyList_Type . CPython ahora tiene que llamar a una función genérica para manejar cualquier objeto llamable llamado _PyObject_FastCallKeywords , yay más llamadas de función.

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

_PyObject_FastCallDict finalmente nos lleva a algún lado! Después de realizar aún más verificaciones , toma la ranura tp_call del type del type que hemos pasado, es decir, agarra type.tp_call . Luego se procede a crear una tupla a partir de los argumentos pasados ​​con _PyStack_AsTuple y, finalmente, ¡se puede hacer una llamada !

tp_call , que coincide con el type.__call__ toma el control y finalmente crea el objeto de lista. Llama a las listas __new__ que corresponde a PyType_GenericNew y le asigna memoria con PyType_GenericAlloc : esta es la parte en la que finalmente se encuentra con PyList_New . Todo lo anterior es necesario para manejar objetos de forma genérica.

Al final, type_call calls list.__init__ e inicializa la lista con los argumentos disponibles, luego regresamos por el mismo camino que vinimos. 🙂

Finalmente, LOAD_NAME el 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 la función C adecuada para hacer el trabajo. No tiene la cortesía de llamarlo de inmediato porque es dynamic, alguien podría enmascarar la list ( y muchas personas lo hacen ) y se debe tomar otro camino.

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

La syntax literal, por otro lado, significa exactamente una cosa; No se puede cambiar y siempre se comporta de forma 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 se mantenga en cualquier versión futura, es la búsqueda dinámica que ralentiza las cosas.

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

La razón principal es que Python trata a la list() como a una función definida por el usuario, lo que significa que puede interceptarla mediante el alias de otra cosa para hacer una list y hacer algo diferente (como usar su propia lista subclasificada o tal vez una deque)

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

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

Explicación

[] se conoce comúnmente como syntax literal.

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

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

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

Una visualización de lista genera 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 proporciona una comprensión, la lista se construye a partir de los elementos que resultan de la comprensión.

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

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

Por otro lado, list() puede ser interceptado desde la creación de una list incorporada utilizando el constructor de listas integradas.

Por ejemplo, digamos 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.') 

Entonces podríamos interceptar la list de list en el ámbito global a nivel de módulo, y luego, cuando creamos una list , creamos nuestra lista de subtipos:

 >>> list = List >>> a_list = list() List initialized. >>> type(a_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)  

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

 >>> list_1 = [] >>> type(list_1)  

Probablemente solo lo hagamos temporalmente, así que deshacemos nuestros cambios: primero eliminemos el nuevo objeto de List de los elementos integrados:

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

Oh, no, perdimos la pista del original.

No se preocupe, aún podemos obtener la list ; es el tipo de literal de lista:

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

Asi que…

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

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

Entonces tenemos que llamar a lo que sea que hayamos llamado. De la gramática:

Una llamada llama a un objeto que se puede llamar (por ejemplo, una función) con una serie de argumentos posiblemente vacíos:

 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 una llamada de función en el nivel de bytecode de 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 en el nivel de bytecode.

Conclusión

Hemos demostrado que la list puede interceptarse con el código de usuario usando las reglas de scope, y esa list() busca un llamador y luego lo llama.

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