Pourquoi les tableaux de Python sont-ils lents?

Question

Je m'attendais à ce que array.array soit plus rapide que les listes, car les tableaux semblent sans boîte.

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?

Answer 1

Le stockage est "unboxed", mais à chaque fois que vous accéder à un élément Python est à la "box" il (l'incorporer dans un objet Python) afin de faire quelque chose avec elle. Par exemple, votre sum(A) parcourt le tableau, et les boîtes de chaque entiers, un à un, dans un Python int objet. Cela coûte du temps. Dans votre sum(L), tout la boxe a été fait au moment où la liste a été créée.

Donc, à la fin, un tableau est généralement plus lent, mais nécessite beaucoup moins de mémoire.

---

Voici le code à partir d'une version récente de Python 3, mais les mêmes idées de base s'appliquent à tous les Disponible implémentations depuis Python a été libéré.

Voici le code pour accéder à un élément de la liste:

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    /* error checking omitted */
    return ((PyListObject *)op) -> ob_item[i];
}

Il y a très peu pour elle: somelist[i] renvoie simplement l' i'th objet de la liste (et tous les objets Python dans Disponible sont des pointeurs vers une structure dont le premier segment est conforme à la disposition d'un struct PyObject).

Et voici l' __getitem__ de la mise en œuvre d'un array avec code de type d' l:

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

La mémoire brute est traitée comme un vecteur de la plate-forme native C long des entiers; l' i'th C long est lire; et puis, PyLong_FromLong() est appelé à envelopper ("box"), le natif C long dans un Python long objet (qui, en Python 3, ce qui élimine Python 2 la distinction entre int et long, est en fait montré que le type int).

Cette boxe a pour allouer de la mémoire pour un Python int objet, et pulvériser le natif C long's bits. Dans le contexte de l'exemple original, cet objet est la durée de vie est très courte (juste assez longtemps pour sum() pour ajouter le contenu en cours d'exécution total), et puis de plus en plus de temps est nécessaire pour libérer la nouvelle - int objet.

C'est là que la différence de vitesse vient de, a toujours viennent toujours viennent de de la Disponible de mise en œuvre.

Answer 2

Pour ajouter à Tim Peters' excellente réponse, les tableaux de mettre en œuvre le protocole de mémoire, tandis que la liste ne pas. Cela signifie que, si vous écrivez un C extension (ou l'équivalent moral, comme la rédaction d'un Cython module), alors vous pouvez accéder et travailler avec les éléments d'un tableau beaucoup plus rapide que ce que Python peut faire. Cela vous donnera une considérable amélioration de la vitesse, probablement bien plus d'un ordre de grandeur. Cependant, il a un certain nombre d'inconvénients:

1. Vous êtes maintenant dans le domaine de l'écriture C au lieu de Python. Cython est un moyen d'améliorer cela, mais il n'élimine pas beaucoup de différences fondamentales entre les langues; vous devez être familier avec le C de la sémantique et de comprendre ce qu'il fait.
2. PyPy est C API travaille dans une certaine mesure, mais n'est pas très rapide. Si vous ciblez les PyPy, vous devriez probablement juste écrire du code simple avec régulièrement des listes, puis laissez-la Gigue de l'optimiser pour vous.
3. C extensions sont plus difficiles à distribuer que pure code Python parce qu'ils ont besoin d'être compilé. Compilation tend à être architecture et dépendante du système d'exploitation, de sorte que vous devez vous assurer que vous compilez pour votre plate-forme cible.

Va directement en C, les extensions peuvent être à l'aide d'un marteau de forgeron d'écraser une mouche, en fonction de votre cas d'utilisation. Vous devriez d'abord enquêter sur NumPy et voir si il est assez puissant pour faire tout ce que les mathématiques que vous essayez de faire. Il sera aussi beaucoup plus rapide que le natif de Python, si elle est utilisée correctement.

Answer 3

Tim Peters répondu pourquoi c'est lent, mais nous allons voir comment améliorer cela.

Tenir à votre exemple de l' sum(range(...)) (facteur 10 plus petite que votre exemple pour tenir en mémoire ici):

import numpy
import array
L = list(range(10**7))
A = array.array('l', L)
N = numpy.array(L)

%timeit sum(L)
10 loops, best of 3: 101 ms per loop

%timeit sum(A)
1 loop, best of 3: 237 ms per loop

%timeit sum(N)
1 loop, best of 3: 743 ms per loop

De cette façon, aussi numpy besoins de boîte/unbox, qui a la charge supplémentaire. Pour faire vite, on doit rester à l'intérieur de la numpy code c:

%timeit N.sum()
100 loops, best of 3: 6.27 ms per loop

Donc, à partir de la liste de la solution à la numpy version, c'est un facteur 16 en runtime.

Nous allons également vérifier combien de temps la création de ces structures de données prend

%timeit list(range(10**7))
1 loop, best of 3: 283 ms per loop

%timeit array.array('l', range(10**7))
1 loop, best of 3: 884 ms per loop

%timeit numpy.array(range(10**7))
1 loop, best of 3: 1.49 s per loop

%timeit numpy.arange(10**7)
10 loops, best of 3: 21.7 ms per loop

Gagnant clair: Numpy

Notez également que la création de la structure de données prend environ autant de temps que la sommation, si pas plus. L'allocation de mémoire est lente.

L'utilisation de la mémoire de ceux:

sys.getsizeof(L)
90000112
sys.getsizeof(A)
81940352
sys.getsizeof(N)
80000096

Donc ces 8 octets par nombre avec divers frais généraux. Pour la gamme que nous utilisons 32bit ints sont suffisantes, nous avons donc pour la sécurité de la mémoire.

N=numpy.arange(10**7, dtype=numpy.int32)

sys.getsizeof(N)
40000096

%timeit N.sum()
100 loops, best of 3: 8.35 ms per loop

Mais il s'avère que l'ajout de 64 bits ints est plus rapide que les entiers 32 bits sur ma machine, donc c'est seulement utile si vous êtes limité par la mémoire/de la bande passante.