Tableau Python efficace avec 100 millions de zéros?

Juste un rappel comment fonctionnent les entiers de Python: Si vous allouez une liste en disant

a = [0] * K

Vous avez besoin de la mémoire pour la liste (sizeof(PyListObject) + K * sizeof(PyObject*)) et de la mémoire pour l'objet entier unique 0. Tant que les nombres dans la liste restent en dessous du nombre magique V que Python utilise pour la mise en cache, vous allez bien parce que ceux-ci sont partagés, c'est-à-dire tout nom qui pointe vers un nombre n < V pointe vers le même objet. Vous pouvez trouver cette valeur en utilisant l'extrait suivant:

>>> i = 0
>>> j = 0
>>> while i is j:
...    i += 1
...    j += 1
>>> i # on my system!
257 

Ce signifie que dès que les comptes vont au-dessus de ce nombre, la mémoire dont vous avez besoin est sizeof(PyListObject) + K * sizeof(PyObject*) + d * sizeof(PyIntObject), Où d < K est le nombre d'entiers au-dessus de V (== 256). Sur un système 64 bits, sizeof(PyIntObject) == 24 et sizeof(PyObject*) == 8, c'est-à-dire que la consommation de mémoire la plus défavorable est de 3 200 000 000 octets.

Avec numpy.ndarray ou array.array, la consommation de mémoire est constante après l'initialisation, mais vous payez pour les objets wrapper créés de manière transparente, comme L'a dit Thomas Wouters. Probablement, vous devriez penser à convertir le code de mise à jour (qui accède et augmente les positions dans le tableau) en code C, soit à l'aide de Cython ou scipy.weave.

Essayez ceci:

x = [0] * 100000000

Il ne faut que quelques secondes pour s'exécuter sur ma machine, et l'accès est proche de l'instant.

Si vous n'êtes pas capable de vectoriser vos calculs, Python / Numpy sera lent. Numpy est rapide car les calculs vectorisés se produisent à un niveau inférieur à celui de Python. Les fonctions numpy de base sont toutes écrites en C ou en Fortran. Par conséquent, sum(a) n'est pas une boucle python avec de nombreux accès, c'est un seul appel C de bas niveau.

Numpy les Performances de Python page de démonstration a un bon exemple avec différentes options. Vous pouvez facilement obtenir une augmentation de 100 fois en utilisant un langage compilé de niveau inférieur, Cython, ou en utilisant des fonctions vectorisées si possible. Cet article de blog {[5] } qui montre une augmentation de 43 fois en utilisant Cython pour un cas d'utilisation numpy.

Il est peu probable que vous trouviez quelque chose de plus rapide que numpy's array. L'implémentation du tableau lui-même est aussi efficace que dans, disons, C (et fondamentalement la même chose que array.array, juste avec plus d'utilité.)

Si vous voulez accélérer votre code, vous devrez le faire par faire exactement cela. Même si le tableau est implémenté efficacement, l'accès à partir du code Python a une certaine surcharge; par exemple, l'indexation du tableau produit des objets entiers, qui doivent être créés à la volée. numpy propose un certain nombre d'opérations implémentées efficacement en C, mais sans voir le code réel qui ne fonctionne pas aussi bien que vous le souhaitez, il est difficile de faire des suggestions spécifiques.

Pour une création rapide, utilisez le module array.

L'Utilisation du module array est ~5 fois plus rapide pour la création, mais environ deux fois plus lente pour accéder aux éléments par rapport à une liste normale:

# Create array
python -m timeit -s "from array import array" "a = array('I', '\x00'
 * 100000000)"
10 loops, best of 3: 204 msec per loop

# Access array
python -m timeit -s "from array import array; a = array('I', '\x00'
* 100000000)" "a[4975563]"
10000000 loops, best of 3: 0.0902 usec per loop

# Create list
python -m timeit "a = [0] * 100000000"
10 loops, best of 3: 949 msec per loop

# Access list
python -m timeit  -s "a = [0] * 100000000" "a[4975563]"
10000000 loops, best of 3: 0.0417 usec per loop

En plus des autres excellentes solutions, une autre façon est d'utiliser un dict au lieu d'un tableau (les éléments qui existent sont non nuls, sinon ils sont nuls). Recherche en temps est O(1).

Vous pouvez également vérifier si votre application réside dans la RAM, plutôt que d'échanger. Ce N'est que 381 Mo, mais le système ne vous donne peut-être pas tout pour une raison quelconque.

Cependant, il y a aussi des matrices clairsemées très rapides ( SciPy et ndsparse). Ils sont fait dans Bas Niveau C, et pourrait aussi être bon.

Je voudrais simplement créer votre propre type de données qui n'initialise aucune valeur.

Si vous voulez lire une position d'index qui N'a pas été initialisée, vous renvoyez des zéros. Pourtant, ne pas initialiser tout stockage.

Si vous voulez lire une position d'index qui a été initialisée, renvoyez simplement la valeur.

Si vous voulez écrire dans une position d'index qui N'a pas été initialisée, initialisez-la et stockez l'entrée.

NumPy est l'outil approprié pour un grand tableau homogène de taille fixe. L'accès à des éléments individuels de N'importe quoi en Python ne sera pas si rapide, bien que les opérations de tableau entier puissent souvent être effectuées à des vitesses similaires à C ou Fortran. Si vous avez besoin d'effectuer des opérations sur des millions et des millions d'éléments individuellement rapidement, il ya seulement tellement que vous pouvez sortir de Python.

Quel type d'algorithme implémentez-vous? Comment savez-vous que l'utilisation de matrices creuses est trop lent si vous n'avez pas essayé? Qu'entendez-vous par "efficace"? Vous voulez une initialisation rapide? C'est le goulot d'étranglement de votre code?

Si

• vitesse d'accès du tableau.tableau est acceptable pour votre application
• le stockage compact est le plus important
• vous voulez utiliser des modules standard (pas de dépendance NumPy)
• Vous êtes sur des plates-formes qui ont / dev / zero

Ce qui suit peut vous intéresser. Il initialise le tableau.array environ 27 fois plus rapide que array.tableau ('L', [0] * Taille):

myarray = array.array('L')
f = open('/dev/zero', 'rb')
myarray.fromfile(f, size)
f.close()

Sur Comment initialiser un tableau d'entiers.objet tableau avec des zéros en Python je suis la recherche d'une meilleure façon de le faire.