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

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

Pourquoi est-ce? Faire []et {}(et probablement ()et ''aussi) passent immédiatement en arrière une copie de certains littérale des actions vides tandis que leurs homologues explicitement nommées ( list(), dict(), tuple(), str()) pleinement s'y prendre pour créer un objet, si elles ont effectivement ou non des éléments?

Je n'ai aucune idée de la différence entre ces deux méthodes, mais j'aimerais le découvrir. Je n'ai pas pu trouver de réponse dans la documentation ou sur SO, et la recherche de parenthèses vides s'est avérée plus problématique que ce à quoi je m'attendais.

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

J'ai récemment découvert « Pourquoi est-ce si vrai plus lent que si 1? » Qui compare les performances de if Trueà if 1et semble toucher à un scénario littéral similaire à celui global; cela vaut peut-être aussi la peine d'être considéré.

Parce que []et {}sont une syntaxe littérale . Python peut créer du bytecode juste pour créer les objets de liste ou de 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 effectué. Tout 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 temporel est probablement une collision de hachage de dictionnaire. Soustrayez ces heures des heures d'appel de ces objets et comparez le résultat avec les heures 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

Le fait d'appeler l'objet prend donc 1.00 - 0.31 - 0.30 == 0.39quelques secondes supplémentaires par 10 millions d'appels.

Vous pouvez éviter le coût de recherche globale en aliasant les noms globaux en tant que locaux (à l'aide d'une timeitconfiguration, 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 ce CALL_FUNCTIONcoût.

list()nécessite une recherche globale et un appel de fonction mais se []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

Parce que listc'est une fonction pour convertir disons une chaîne en un objet liste, tandis que []est utilisé pour créer une liste dès le départ. Essayez ceci (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.

Les réponses ici sont excellentes, précises et couvrent entièrement cette question. Je laisserai tomber une étape supplémentaire du code octet pour les personnes intéressées. J'utilise le dépôt le plus récent de CPython; les anciennes versions se comportent de manière similaire à cet égard, mais de légères modifications pourraient être en place.

Voici une ventilation de l'exécution de chacun d'eux, BUILD_LISTpour []et CALL_FUNCTIONpour list().

L' BUILD_LISTinstruction:

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. Voici à quel point c'est simple:

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

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

L' CALL_FUNCTIONinstruction:

Voici la première chose que vous voyez lorsque vous jetez un œ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();

Semble assez inoffensif, non? Eh bien, non, malheureusement non, ce call_functionn'est pas un gars simple qui appellera la fonction immédiatement, il ne peut pas. Au lieu de cela, il récupère l'objet de la pile, récupère tous les arguments de la pile, puis bascule en fonction du type de l'objet; est-ce un:

• PyCFunction_Type? Non, il est list, listest pas de typePyCFunction
• PyMethodType? Non, voir précédent.
• PyFunctionType? Nopee, voir précédent.

Nous appelons le listtype, l'argument transmis à call_functionest 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 vérifie à nouveau certains types de fonctions (dont je ne comprends pas pourquoi) puis, après avoir créé un dict pour kwargs si nécessaire , continue à appeler _PyObject_FastCallDict.

_PyObject_FastCallDictnous emmène enfin quelque part! Après avoir effectué encore plus de vérifications, il saisit l' tp_callemplacement de celuitype que typenous avons passé, c'est-à-dire qu'il saisit type.tp_call. Il procède ensuite à la création d'un tuple à partir des arguments passés avec _PyStack_AsTupleet, enfin, un appel peut enfin être effectué !

tp_call, qui correspond type.__call__prend le relais et crée finalement l'objet liste. Il appelle les listes __new__qui lui correspondent PyType_GenericNewet lui alloue de la mémoire avec PyType_GenericAlloc: C'est en fait la partie où il se rattrape PyList_New, enfin . Toutes les précédentes sont nécessaires pour gérer les objets de manière générique.

En fin de compte, type_callappelle list.__init__et initialise la liste avec tous les arguments disponibles, puis nous revenons sur notre chemin. :-)

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

Il est facile de voir que, lorsqu'il s'agit de notre entrée, Python doit généralement sauter à travers des cerceaux afin de trouver réellement la Cfonction appropriée pour faire le travail. Il n'a pas la courtoisie de l'appeler immédiatement car il est dynamique, quelqu'un peut masquer list( et le garçon fait beaucoup de gens ) et un autre chemin doit être emprunté.

C'est là que list()perd beaucoup: l'exploration de Python doit faire pour savoir ce qu'il doit faire.

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

^{Note de bas de page: Tous les noms de fonction sont susceptibles de changer d'une version à l'autre. Le point est toujours d'actualité et se maintiendra probablement dans toutes les versions futures, c'est la recherche dynamique qui ralentit les choses.}

Pourquoi est []plus rapide que list()?

La principale raison est que Python est traité list()comme une fonction définie par l'utilisateur, ce qui signifie que vous pouvez l'intercepter en aliasant quelque chose d'autre listet en faisant quelque chose de différent (comme utiliser votre propre liste de sous-classes ou peut-être un deque).

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

Mon explication cherche à vous en donner l'intuition.

Explication

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

Dans la grammaire, cela est appelé un "affichage de liste". De la documentation :

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

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

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

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

Il n'y a aucun moyen de contourner cela - ce qui signifie que Python peut le faire aussi rapidement qu'il le peut.

D'un autre côté, il list()peut être intercepté de créer une fonction intégrée listà l'aide du constructeur de liste intégrée.

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 listsur la portée globale au niveau du module, puis lorsque nous créons un list, nous créons en fait notre liste de sous-types:

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

De même, nous pourrions le supprimer 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 la liste crée une liste sans condition:

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

Nous ne le faisons probablement que temporairement, alors annulons nos modifications - Listsupprimons d' abord le nouvel objet des commandes internes:

>>> 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 vous inquiétez pas, nous pouvons toujours obtenir list- c'est le type d'une liste littérale:

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

Donc...

Pourquoi est []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, listnous devons faire des recherches pour voir s'il y a quelque chose.

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

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

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

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

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

Cela va simplement à la construction de la liste sans recherche ni appel au niveau du bytecode.

Conclusion

Nous avons démontré qu'il listpeut être intercepté avec du code utilisateur à l'aide des règles de portée, et qu'il list()recherche un appelable, puis l'appelle.

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