Je m'attendais array.array
à être plus rapide que les listes, car les tableaux semblent être déballés.
Cependant, j'obtiens le résultat suivant:
In [1]: import array
In [2]: L = list(range(100000000))
In [3]: A = array.array('l', range(100000000))
In [4]: %timeit sum(L)
1 loop, best of 3: 667 ms per loop
In [5]: %timeit sum(A)
1 loop, best of 3: 1.41 s per loop
In [6]: %timeit sum(L)
1 loop, best of 3: 627 ms per loop
In [7]: %timeit sum(A)
1 loop, best of 3: 1.39 s per loop
Quelle pourrait être la cause d'une telle différence?
python
arrays
performance
boxing
python-internals
Valentin Lorentz
la source
la source
array
package. Si vous voulez faire des quantités significatives de mathématiques, Numpy fonctionne à la vitesse de la lumière (c'est-à-dire C), et généralement mieux que les implémentations naïves de choses commesum()
).array
conversion d'une chaîne d'entiers (représentant des octets ASCII) en unstr
objet est assez rapide . Guido lui-même n'a proposé cela qu'après de nombreuses autres solutions et a été assez surpris de la performance. Quoi qu'il en soit, c'est le seul endroit où je me souviens de l'avoir vu être utile.numpy
est bien meilleur pour traiter les tableaux, mais c'est une dépendance tierce.Réponses:
Le stockage est "déballé", mais chaque fois que vous accédez à un élément, Python doit le "boxer" (l'incorporer dans un objet Python normal) pour pouvoir faire quoi que ce soit avec lui. Par exemple, votre
sum(A)
itère sur le tableau et encadre chaque entier, un à la fois, dans unint
objet Python normal . Cela prend du temps. Dans votresum(L)
, toute la boxe a été faite au moment où la liste a été créée.Ainsi, à la fin, un tableau est généralement plus lent, mais nécessite beaucoup moins de mémoire.
Voici le code pertinent d'une version récente de Python 3, mais les mêmes idées de base s'appliquent à toutes les implémentations de CPython depuis la sortie de Python.
Voici le code pour accéder à un élément de liste:
Il n'y a pas grand-chose à faire:
somelist[i]
renvoie simplement lei
'ième objet de la liste (et tous les objets Python en CPython sont des pointeurs vers une structure dont le segment initial est conforme à la disposition de astruct PyObject
).Et voici l'
__getitem__
implémentation pour unarray
code avec typel
:La mémoire brute est traitée comme un vecteur d'
C
long
entiers natifs de la plate-forme ; lei
'thC long
est lu; etPyLong_FromLong()
est ensuite appelé pour envelopper ("box") le natifC long
dans unlong
objet Python (qui, en Python 3, qui élimine la distinction de Python 2 entreint
etlong
, est en fait montré comme typeint
).Ce boxing doit allouer une nouvelle mémoire pour un
int
objet Python , et y pulvériser lesC long
bits du natif . Dans le contexte de l'exemple d'origine, la durée de vie de cet objet est très brève (juste assez longue poursum()
ajouter le contenu dans un total en cours), puis plus de temps est nécessaire pour désallouer le nouvelint
objet.C'est de là que la différence de vitesse vient, est toujours venue et proviendra toujours dans l'implémentation CPython.
la source
Pour ajouter à l'excellente réponse de Tim Peters, les tableaux implémentent le protocole de tampon , contrairement aux listes. Cela signifie que, si vous écrivez une extension C (ou l'équivalent moral, comme l'écriture d'un Cython module ), vous pouvez accéder et travailler avec les éléments d'un tableau beaucoup plus rapidement que tout ce que Python peut faire. Cela vous donnera des améliorations de vitesse considérables, peut-être bien sur un ordre de grandeur. Cependant, il présente un certain nombre d'inconvénients:
Pour passer directement aux extensions C, il se peut que vous utilisiez un marteau pour écraser une mouche, selon votre cas d'utilisation. Vous devriez d'abord étudier NumPy et voir s'il est assez puissant pour faire tout ce que vous essayez de faire. Il sera également beaucoup plus rapide que Python natif, s'il est utilisé correctement.
la source
Tim Peters a répondu pourquoi c'était lent, mais voyons comment l'améliorer .
S'en tenir à votre exemple de
sum(range(...))
(facteur 10 plus petit que votre exemple pour tenir dans la mémoire ici):De cette façon, numpy doit également boxer / déballer, ce qui a une surcharge supplémentaire. Pour le rendre rapide, il faut rester dans le code numpy c:
Donc, de la solution de liste à la version numpy, il s'agit d'un facteur 16 à l'exécution.
Vérifions également combien de temps prend la création de ces structures de données
Vainqueur clair: Numpy
Notez également que la création de la structure de données prend à peu près autant de temps que la sommation, sinon plus. L'allocation de mémoire est lente.
Utilisation de la mémoire de ceux-ci:
Donc, ceux-ci prennent 8 octets par nombre avec des frais généraux variables. Pour la gamme, nous utilisons des ints 32 bits sont suffisants, nous pouvons donc conserver de la mémoire.
Mais il s'avère que l'ajout d'ints 64 bits est plus rapide que les ints 32 bits sur ma machine, donc cela ne vaut la peine que si vous êtes limité par la mémoire / la bande passante.
la source
veuillez noter que
100000000
équivaut à10^8
ne pas faire10^7
, et mes résultats sont les suivants:la source