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


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

¿Por qué es esto? Hacer [] y {} (y probablemente () y '', también) inmediatamente devuelven copias de algunas existencias vacías literales mientras sus contrapartes explícitamente nombradas (list(), dict(), tuple(), str()) completamente crear un objeto, si tienen o no elementos?

No tengo idea de cómo difieren estos dos métodos, pero me gustaría saberlo. No pude encontrar una respuesta en los documentos o en SO, y buscar los corchetes vacíos resultó ser más problemático de lo que esperaba.

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

Descubrí recientemente "¿Por qué si es True más lento que si 1?"eso compara el rendimiento de if True a if 1 y parece tocar un escenario literal similar versus global; quizás vale la pena considerarlo también.


587
2018-05-13 13:16


origen


Respuestas:


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 ser resueltos, la pila debe estar involucrada para empujar los argumentos, el cuadro debe ser almacenado para recuperarlo más tarde, y debe hacerse 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í __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 sincronizar la búsqueda de nombre 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 sea una colisión hash de diccionario. Reste esos tiempos de los tiempos para llamar a esos objetos, y compare el resultado con los tiempos para usar los 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 requiere un 1.00 - 0.31 - 0.30 == 0.39 segundos por 10 millones de llamadas.

Puede evitar el costo de búsqueda global al alias de los nombres globales como locales (utilizando un timeit configuración, todo lo que enlaza 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 eso CALL_FUNCTION costo.


654
2018-05-13 13:21



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

128
2018-05-13 13:22



Porque list es un función convertir una cadena en un objeto de lista, mientras [] se usa para crear una lista del bate. Pruebe esto (podría 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.


70
2018-05-13 13:21



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

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


los BUILD_LIST instrucción:

Deberías simplemente 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 intrincado, lo sé. Esto es lo simple que es:

  • Crea una nueva lista con PyList_New (esto asigna principalmente la memoria para un nuevo objeto de lista), oparg señalando el número de argumentos en la pila. Directo al grano.
  • Verifique que nada salió mal con 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 :-)

los CALL_FUNCTION instrucción:

Esto es lo primero que verá cuando eche un vistazo al 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, lamentablemente no, call_function no es un tipo sencillo que llamará a la función de inmediato, no puede. En cambio, toma el objeto de la pila, toma todos los argumentos de la pila y luego cambia según el tipo de objeto; Es una:

Estamos llamando al list tipo, el argumento pasó 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 hacer 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 requerido, continúa para llamar _PyObject_FastCallDict.

_PyObject_FastCallDict finalmente nos lleva a algún lado! Después de realizar aún más cheques  eso agarra el tp_call ranura de la type del type hemos pasado, es decir, atrapa type.tp_call. Luego procede a crear una tupla de los argumentos pasados ​​con _PyStack_AsTuple y finalmente, una llamada finalmente puede hacerse!

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

En el final, type_call llamadas list.__init__ e inicializa la lista con cualquier argumento disponible, luego volvemos por donde llegamos. :-)

Finalmente, remmeber el LOAD_NAME, ese es otro chico que contribuye aquí.


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

Aquí es donde list() pierde mucho: la exploración de Python tiene que 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 una manera predeterminada.

Nota al pie: todos los nombres de las 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.


10
2017-12-02 19:01



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

La razón principal es que Python trata list() como una función definida por el usuario, lo que significa que puede interceptarla aliasing algo más para list y hacer algo diferente (como usar tu propia lista subclasificada o quizás 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 de expresiones posiblemente vacía incluida en   corchetes:

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

Una visualización de lista produce un nuevo objeto de lista, los contenidos que se especifican   por una lista de expresiones o una comprensión. Cuando un   lista de expresiones separadas por comas, sus elementos son   evaluado de izquierda a derecha y colocado en el objeto de la lista en ese   orden. Cuando se proporciona una comprensión, la lista se construye a partir de   los elementos resultantes de la comprensión.

En resumen, esto significa que un objeto incorporado de tipo list es creado.

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

Por otra parte, list() puede ser interceptado desde la creación de un builtin list 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.')

Podríamos interceptar el nombre list en el ámbito global a nivel de módulo, y luego cuando creamos un list, realmente creamos nuestra lista subtipificada:

>>> 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 lista de visualización crea una lista incondicionalmente:

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

Probablemente solo lo hagamos temporalmente, así que podemos deshacer nuestros cambios: primero elimine el nuevo List objeto de los builtins:

>>> 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 la pista del original.

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

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

Asi que...

Por que 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 list tenemos que hacer las búsquedas para ver si hay algo allí.

Luego tenemos que llamar a lo que sea invocable que hayamos buscado. De la gramática:

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

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

por [] no hay 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 creación de la lista sin búsquedas o llamadas en el nivel de código de bytes.

Conclusión

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

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


5
2017-11-27 14:20