Question Pourquoi est-ce que [] est plus rapide que list ()?


J'ai récemment comparé les vitesses de traitement de [] et list() et a été surpris de découvrir que [] fonctionne plus de trois fois plus vite que list(). J'ai couru le même test avec {} et dict() et les résultats étaient pratiquement identiques: [] et {} les deux ont pris environ 0.128sec / million de cycles, tandis que list() et dict() a pris environ 0,428sec / million de cycles chacun.

Pourquoi est-ce? Faire [] et {} (et probablement () et '', aussi) repasser immédiatement des copies de certains titres littéraux vides pendant que leurs homologues explicitement nommés (list(), dict(), tuple(), str()) va-t-il complètement créer un objet, qu'il ait ou non des éléments?

Je n'ai aucune idée de la différence entre ces deux méthodes, mais j'aimerais bien le savoir. Je n'ai pas trouvé de réponse dans les docs ou sur SO, et la recherche de parenthèses vides s'est révélée être plus problématique que ce à quoi je m'attendais.

J'ai obtenu mes résultats de synchronisation en appelant timeit.timeit("[]") et timeit.timeit("list()"), et timeit.timeit("{}") et timeit.timeit("dict()"), pour comparer les listes et les dictionnaires, respectivement. Je cours Python 2.7.9.

J'ai récemment découvert "Pourquoi est-ce si Vrai plus lent que si 1?"qui compare la performance de if True à if 1 et semble toucher un scénario littéral-versus-similaire similaire; peut-être que cela vaut la peine d'être pris en compte.


587
2018-05-13 13:16


origine


Réponses:


Car [] et {} sont syntaxe littérale. Python peut créer un bytecode juste pour créer les objets liste ou dictionnaire:

>>> 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() et dict() sont des objets séparés. Leurs noms doivent être résolus, la pile doit être impliquée pour pousser les arguments, la trame doit être stockée pour être récupérée plus tard, et un appel doit être fait. Cela prend plus de temps.

Pour le cas vide, cela signifie que vous avez au moins un LOAD_NAME (qui doit rechercher à travers l'espace de noms global ainsi que le __builtin__ module) suivi d'un CALL_FUNCTION, qui doit conserver le cadre actuel:

>>> 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        

Vous pouvez chronométrer la recherche de nom séparément avec timeit:

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

L'écart de temps est probablement une collision de hachage de dictionnaire. Soustrayez ces temps des heures d'appel de ces objets et comparez le résultat avec les temps d'utilisation des littéraux:

>>> 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

Donc, avoir à appeler l'objet prend une autre 1.00 - 0.31 - 0.30 == 0.39 secondes par 10 millions d'appels.

Vous pouvez éviter le coût de recherche global en aliasant les noms globaux en tant que locals (en utilisant un timeit configuration, tout ce que vous liez à un nom est 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

mais vous ne pouvez jamais surmonter cela CALL_FUNCTION Coût.


654
2018-05-13 13:21



list() nécessite une recherche globale et un appel de fonction, mais [] compile en une seule instruction. Voir:

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



Car list est un fonction convertir une chaîne en un objet liste, alors que [] est utilisé pour créer une liste de la chauve-souris. Essayez ceci (cela pourrait vous sembler plus logique):

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

Tandis que

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

Vous donne une liste réelle contenant tout ce que vous y mettez.


70
2018-05-13 13:21



Les réponses sont excellentes, pertinentes et couvrent entièrement cette question. Je vais laisser tomber un autre pas de byte-code pour ceux qui sont intéressés. J'utilise le repo le plus récent de CPython; les versions plus anciennes se comportent de la même manière à cet égard, mais de légères modifications peuvent être en place.

Voici une répartition de l'exécution pour chacun d'entre eux, BUILD_LIST pour [] et CALL_FUNCTION pour list().


le BUILD_LIST instruction:

Vous devriez juste voir l'horreur:

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();

Terriblement alambiqué, je sais. C'est comme c'est simple:

  • Créer une nouvelle liste avec PyList_New (ceci alloue principalement la mémoire pour un nouvel objet de liste), oparg signaler le nombre d'arguments sur la pile. Droit au but.
  • Vérifiez que rien ne s'est mal passé avec if (list==NULL).
  • Ajoutez des arguments (dans notre cas, ce n'est pas exécuté) situés sur la pile avec PyList_SET_ITEM (une macro).

Pas étonnant que ce soit rapide! C'est fait sur mesure pour créer de nouvelles listes, rien d'autre :-)

le CALL_FUNCTION instruction:

Voici la première chose que vous voyez lorsque vous jetez un coup d'œil à la gestion du code 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();

Ça a l'air assez inoffensif, non? Eh bien, non, malheureusement pas, call_function n'est pas un gars simple qui appellera la fonction immédiatement, il ne peut pas. Au lieu de cela, il saisit l'objet de la pile, attrape tous les arguments de la pile, puis bascule en fonction du type de l'objet; est-ce un:

Nous appelons le list type, l'argument transmis à call_function est PyList_Type. CPython doit maintenant appeler une fonction générique pour gérer tous les objets appelables nommés _PyObject_FastCallKeywords, yay plus d'appels de fonction.

Cette fonction effectue à nouveau des vérifications pour certains types de fonctions (que je ne comprends pas pourquoi) et ensuite, après avoir créé un dict pour kwargs si nécessaire, continue à appeler _PyObject_FastCallDict.

_PyObject_FastCallDict nous obtient finalement quelque part! Après avoir joué encore plus de contrôles  il attrape le tp_call emplacement de la type du type nous avons passé, c'est-à-saisir type.tp_call. Il procède ensuite à créer un tuple sur les arguments passés avec _PyStack_AsTuple et enfin, un appel peut enfin être fait!

tp_call, qui correspond type.__call__ prend le dessus et crée finalement l'objet liste. Il appelle les listes __new__ ce qui correspond à PyType_GenericNew et alloue de la mémoire pour cela avec PyType_GenericAlloc: C'est en fait la partie où il rattrape PyList_New, enfin. Tous les précédents sont nécessaires pour gérer les objets de manière générique.

À la fin, type_call appels list.__init__ et initialise la liste avec tous les arguments disponibles, puis nous revenons sur la façon dont nous sommes arrivés. :-)

Enfin, rappelez-vous LOAD_NAME, c'est un autre gars qui contribue ici.


Il est facile de voir que, lorsqu'il s'agit de notre contribution, Python doit généralement passer par des cerceaux afin de trouver le bon C fonction pour faire le travail. Il n'a pas la courtoisie de l'appeler immédiatement parce que c'est dynamique, quelqu'un pourrait masquer list (et le garçon fait beaucoup de gens) et un autre chemin doit être pris.

C'est ici que list() perd beaucoup: L'explorateur Python doit faire pour découvrir ce qu'il devrait faire.

D'autre part, la syntaxe littérale signifie exactement une chose; il ne peut pas être changé et se comporte toujours d'une manière prédéterminée.

Note de bas de page: Tous les noms de fonctions peuvent changer d'une version à l'autre. Le point est toujours d'actualité et il est fort probable que ce soit dans les futures versions, c'est la recherche dynamique qui ralentit les choses.


10
2017-12-02 19:01



Pourquoi est-ce [] plus rapide que list()?

La plus grande raison est que les friandises Python list() juste comme une fonction définie par l'utilisateur, ce qui signifie que vous pouvez l'intercepter en aliasant quelque chose d'autre à list et faire quelque chose de différent (comme utiliser votre propre liste sous-classée ou peut-être une deque).

Il crée immédiatement une nouvelle instance d'une liste intégrée avec [].

Mon explication cherche à vous donner l'intuition pour cela.

Explication

[] est communément appelé syntaxe littérale.

Dans la grammaire, ceci est appelé "affichage de liste". De la docs:

Un affichage de liste est une série d'expressions éventuellement vide   crochets:

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

Un affichage de liste donne un nouvel objet de liste, le contenu étant spécifié   soit par une liste d'expressions ou une compréhension. Lorsqu'un   liste d'expressions séparées par des virgules est fournie, ses éléments sont   évalué de gauche à droite et placé dans l'objet de la liste dans ce   commande. Quand une compréhension est fournie, la liste est construite à partir de   les éléments résultant de la compréhension.

En bref, cela signifie qu'un objet intégré de type list est créé.

Il n'y a pas de contournement - ce qui signifie que Python peut le faire aussi rapidement que possible.

D'autre part, list() peut être intercepté de la création d'un builtin list en utilisant le constructeur de liste intégré.

Par exemple, disons que nous voulons que nos listes soient créées bruyamment:

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

Nous pourrions alors intercepter le nom list sur la portée globale du niveau du module, puis lorsque nous créons un list, nous créons en fait notre liste sous-typée:

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

De même, nous pourrions le retirer de l'espace de noms global

del list

et le mettre dans l'espace de noms intégré:

import builtins
builtins.list = List

Et maintenant:

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

Et notez que l'affichage de liste crée une liste inconditionnellement:

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

Nous ne faisons probablement cela que temporairement, donc nous allons annuler nos changements - d'abord retirer le nouveau List objet des 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 non, nous avons perdu la trace de l'original.

Ne pas s'inquiéter, nous pouvons toujours obtenir list - C'est le type d'une liste littérale:

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

Alors...

Pourquoi est-ce [] plus rapide que list()?

Comme nous l'avons vu - nous pouvons écraser list - mais nous ne pouvons pas intercepter la création du type littéral. Lorsque nous utilisons list nous devons faire les recherches pour voir si quelque chose est là.

Ensuite, nous devons appeler tout appelable que nous avons recherché. De la grammaire:

Un appel appelle un objet appelable (par exemple, une fonction) avec éventuellement   série vide d'arguments:

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

Nous pouvons voir qu'il fait la même chose pour n'importe quel nom, pas seulement pour la liste:

>>> 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

Pour [] il n'y a pas d'appel de fonction au niveau du bytecode Python:

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

Il va simplement directement à la construction de la liste sans aucune recherche ou appel au niveau du bytecode.

Conclusion

Nous avons démontré que list peut être intercepté avec le code utilisateur en utilisant les règles de portée, et que list()cherche un appelable, puis l'appelle.

Tandis que [] est un affichage de liste, ou un littéral, et évite ainsi la recherche de nom et l'appel de fonction.


5
2017-11-27 14:20