Pourquoi [] est plus rapide que list()?

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

pourquoi? Faire [] et {} (et probablement () et '' ) immédiatement transmettre une copie de certains vides stock littéral, tandis que leurs explicitement nommées homologues ( list() , dict() , tuple() , str() ) entièrement d'aller sur la création d'un objet, si oui ou non ils ont effectivement des éléments?

je n'ai aucune idée de comment ces deux méthodes diffèrent, mais j'aimerais savoir. Je ne pouvais pas trouver une réponse dans les docs ou alors, et chercher des crochets vides s'est avéré être plus problématique que je m'y 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. Je lance 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 1 et semble pour aborder un scénario similaire littéral-contre-global; peut-être cela vaut-il la peine d'envisager aussi.

596
demandé sur Community 2015-05-13 16:16:22
la source

5 ответов

parce que [] et {} sont syntaxe littérale . Python peut créer bytecode juste pour créer la liste ou les objets du 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 distincts. Leurs noms doivent être résolus, la pile doit être impliqué pour pousser les arguments, l'image doit être stockée à récupérer plus tard, et un appel sera fait. Que tout 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 préserver 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 il ya probablement une dictionnaire hash collision. Soustrayez ces temps des temps pour appeler ces objets, et comparez le résultat avec les temps pour utiliser les littérales:

>>> 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 un 1.00 - 0.31 - 0.30 == 0.39 secondes supplémentaires pour 10 millions d'appels.

vous pouvez éviter le coût de la recherche globale en alienant les noms globaux comme des locaux (en utilisant un timeit setup, 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 coût CALL_FUNCTION .

662
répondu Martijn Pieters 2015-05-13 16:40:48
la source

list() nécessite une recherche globale et un appel de fonction mais [] compile à 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
129
répondu Dan D. 2015-05-13 22:22:23
la source

parce que list est une fonction pour convertir say string en un objet list, tandis que [] est utilisé pour créer une liste à partir de la batte. Essayez ceci (pourrait faire plus de sens pour vous):

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

, Alors que

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

vous donne une liste contenant ce que vous y avez mis.

72
répondu Torxed 2015-05-13 16:27:34
la source

Les réponses ici sont grands, au point et à la couvrir entièrement à cette question. Je vais laisser tomber un autre pas vers le bas de byte-code pour ceux qui sont intéressés. J'utilise le rapport le plus récent de CPython; les versions plus anciennes se comportent de la même manière à cet égard, mais de légers changements pourraient être en place.

voici une répartition de l'exécution pour chacun de ceux-ci, BUILD_LIST pour [] et CALL_FUNCTION pour list() .


le BUILD_LIST instruction:

vous devriez Vous contenter de la vue de 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 aussi simple que cela:

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

pas étonnant qu'il 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 quand vous regardez à le code de manipulation 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 plutôt inoffensif, non? Eh bien, non, malheureusement pas, call_function n'est pas un gars simple qui va appeler la fonction immédiatement, il ne peut pas. Au lieu de cela, il saisit l'objet à partir de la pile, saisit tous les arguments de la pile et puis commute en fonction du type de l'objet; est-il un:

nous appelons le type list , l'argument passé à call_function est PyList_Type . Disponible maintenant appeler une fonction générique pour gérer tout appelable les objets nommés _PyObject_FastCallKeywords , yay plus d'appels de fonction.

cette fonction effectue à nouveau quelques vérifications pour certains types de fonctions (que je ne peux pas comprendre pourquoi) et puis, après avoir créé un dict pour kwargs si nécessaire , va à l'appel _PyObject_FastCallDict .

_PyObject_FastCallDict nous mène quelque part! Après avoir effectué encore plus de contrôles it prend la fente tp_call du type du type nous sommes passés, c'est-à-dire qu'il prend type.tp_call . Il procède ensuite à créer un tuple à partir des arguments passés avec _PyStack_AsTuple et, enfin, un appel peut enfin être fait !

tp_call , qui correspond à type.__call__ prend la relève et crée finalement l'objet list. Il appelle la liste __new__ qui correspond à PyType_GenericNew et lui attribue de la mémoire avec PyType_GenericAlloc : c'est en fait la partie où il rattrape PyList_New , finalement . Tous les précédents sont nécessaires pour manipuler des objets de façon générique.

En fin de compte, type_call appels list.__init__ et initialise la liste avec tous les arguments disponibles, puis nous partons faire un retour de la même manière que nous sommes venus. :- )

enfin, remmeber le LOAD_NAME , c'est un autre gars qui contribue ici.


il est facile de voir que, lorsque nous traitons notre entrée, Python doit généralement Sauter à travers des cerceaux afin de trouver réellement la fonction C appropriée pour faire le travail. Il n'a pas la réduction de l'appeler immédiatement parce que c'est dynamique, quelqu'un pourrait masquer list ( et garçon font beaucoup de gens font ) et un autre chemin doit être pris.

c'est là que list() perd beaucoup: le python explorateur doit faire pour savoir ce qu'il devrait faire.

la syntaxe littérale, d'un autre côté, signifie exactement une chose; elle ne peut pas être changée et se comporte toujours d'une manière prédéterminée.

Note: Tous les noms de fonction peuvent changer d'une version à l'autre. Le point reste et restera très probablement dans toutes les versions futures, c'est la recherche dynamique qui ralentit les choses.

11
répondu Jim Fasarakis Hilliard 2017-04-01 21:35:33
la source

pourquoi [] est plus rapide que list() ?

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

il crée immédiatement une nouvelle instance d'une liste avec [] .

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

explication

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

dans la grammaire, il s'agit d'un"affichage de liste". à Partir de la documentation :

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

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

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

en bref, cela signifie qu'un objet construit de type list est créé.

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

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

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 au niveau du module portée globale, et puis quand 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 mondial

del list

et mettez-le dans l'espace de nom de construction:

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 permet donc d'annuler temporairement nos modifications - d'abord supprimer le nouvel objet List 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 vous inquiétez Pas, nous pouvons toujours obtenir list - c'est le type d'une liste littérale:

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

So...

pourquoi [] est plus rapide que list() ?

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

alors nous devons appeler n'importe quel appel que nous avons cherché. De la grammaire:

un appel appelle un objet appelant (par exemple, une fonction) avec une possibilité 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 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 tout simplement directement à la construction de la liste sans aucune recherche ou appels au niveau du bytecode.

Conclusion

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

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

5
répondu Aaron Hall 2018-06-17 02:25:25
la source