python matplotlib - Pourquoi les tableaux de Python sont-ils lents?




2 Answers

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) afin de faire quoi que ce soit avec lui. Par exemple, votre sum(A) itère sur le tableau et place chaque entier, un à la fois, dans un objet Python int normal. Cela coûte du temps. Dans votre sum(L) , toute la boxe a été faite au moment de la création de la liste.

Donc, à 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:

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

Il y a très peu de chose: somelist[i] retourne juste le i 'ième objet dans la liste (et tous les objets Python dans CPython sont des pointeurs vers une structure dont le segment initial est conforme à la structure d'un struct PyObject ).

Et voici l'implémentation de __getitem__ pour un array avec le code de type 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 d'entiers long C natifs de la plate-forme; le i 'ième C long est lu; puis PyLong_FromLong() est appelé à envelopper ("box") le C long natif dans un long objet Python (ce qui, en Python 3, qui élimine la distinction de Python 2 entre int et long , est en fait montré comme un type int ).

Cette boxe doit allouer de la nouvelle mémoire pour un objet int Python, et pulvériser les bits de C long natifs dans celui-ci. Dans le contexte de l'exemple original, la durée de vie de cet objet est très courte (juste assez longtemps pour que sum() ajoute le contenu dans un total cumulé), puis plus de temps est nécessaire pour libérer le nouvel objet int .

C'est de là que vient la différence de vitesse, provient toujours de l'implémentation de CPython et viendra toujours d'elle.

ne library

Je m'attendais à ce que array.array soit plus rapide que les listes, car les tableaux semblent être 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?




Tim Peters a répondu pourquoi c'est lent, mais voyons comment l'améliorer .

Coller à votre exemple de sum(range(...)) (facteur 10 plus petit que votre exemple pour tenir dans la 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, numpy doit également être en boîte / unbox, ce qui a un surcoût supplémentaire. Pour le rendre rapide, il faut rester dans le code c:

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

Donc, de la solution liste à la version numpy, il y a un facteur 16 dans l'exécution.

Vérifions également la durée de création de ces structures de données

%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

Vainqueur clair: Numpy

Notez également que la création de la structure de données prend à peu près autant de temps que la somme, sinon 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, ceux-ci prennent 8 octets par nombre avec des frais généraux variables. Pour la gamme que nous utilisons, les en-bits 32 bits sont suffisants, donc nous pouvons sauvegarder 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 est plus rapide que celui de 32 bits sur ma machine, donc cela ne vaut que si vous êtes limité par la mémoire / bande passante.




Related

python arrays performance boxing python-internals