Combien d'éléments peut contenir un dictionnaire Python ?

Question

Je viens d'obtenir la sortie suivante dans la console Python en utilisant Windows 7 64 bits et Python 2.7 32 bits :

>>> a = {}
>>> for k in xrange(1000000): a[k] = k
...
Traceback (most recent call last):
  File "", line 1, in 
MemoryError
>>> len(a)
21846
>>> a[21846]
Traceback (most recent call last):
  File "", line 1, in 
KeyError: 21846
>>> a[21846] = 21846
Traceback (most recent call last):
  File "", line 1, in 
MemoryError

Pourquoi je ne peux pas ajouter plus de 21846 éléments dans le dictionnaire ?

Qu'est-ce qui est spécifique à ce nombre (2 * 3 * 11 * 331) ?

Remarque : J'ai beaucoup plus de RAM que sys.getsizeof(a) == 393356

Answer 1

Très surprenant! Il n'y a rien de spécial à propos de Python en ce qui concerne 21846. Voici sur Windows Vista 32 bits avec Python 2.7.5 et un modeste 3 Go de RAM :

>>> a = {}
>>> for k in xrange(1000000): a[k] = k
...
>>> len(a)
1000000

Peut également le faire avec 10 millions. Mais ceci était en commençant avec une nouvelle fenêtre de console. Peut-être avez-vous fait d'autres choses avant ce que vous nous avez montré, et avez laissé derrière vous de grandes structures de données ? 21846 est minime selon les normes modernes ;-)

Plus tard

Cela a été publié sur le suivi des bugs de Python, ici : http://bugs.python.org/issue19246

Cela a été fermé comme "ne sera pas corrigé", car le même type de comportement a été reproduit par un simple petit programme pur en C. C'est-à-dire que le malloc() et le free() du système C sont coupables, et il n'y a rien qu'un Python sain puisse y faire. Cela semble spécifique à Windows, en utilisant les bibliothèques C de Microsoft. Le problème est la fragmentation du tas : après avoir alloué et libéré de nombreux objets de tailles différentes, le malloc() du système échoue alors lorsqu'on lui demande un bloc de mémoire "assez grand", malgré qu'il y ait plein d'octets libres disponibles. Mais ils ne sont pas dans un seul morceau contigu (du moins pas dans un que le malloc() du système reconnaît comme tel).

Des choses arrivent ;-)

Answer 2

C'est une contrainte de votre environnement et n'a rien à voir avec les dictionnaires Python. Donc, la réponse à votre question est : un dictionnaire Python peut contenir autant que votre environnement le permet.

Answer 3

Comme @Leifingson et @Tim l'ont mentionné, ce comportement dépend des actions effectuées précédemment. Pour illustrer la consommation de mémoire, je vais utiliser l'exemple suivant :

Python 2.7 (r27:82525, 4 juil. 2010, 09:01:59) [MSC v.1500 32 bits (Intel)] sur win32
Tapez "help", "copyright", "credits" ou "license" pour plus d'informations.
>>> a = {}
>>> for k in xrange(1000000): a['a' * k] = k
...
Traceback (most recent call last):
  File "", line 1, in 
MemoryError
>>> len(a)
64036

Si nous prenons la longueur totale des clés :

>>> log(sum(xrange(64036)), 2)
30.93316861532543

nous obtenons près du débordement d'entier !

La partie délicate est :

>>> import sys
>>> sys.getsizeof(a)
1573004

sys.getsizeof retourne la taille de quelque chose de différent des éléments du dictionnaire. Peut-être s'agit-il de la taille de tous les hachages de clés, je ne sais pas.

Après cela :

>>> a = {}

libérera toute la mémoire allouée de 2 Go, mais laissera le GC (je le blâme) dans un état quelque peu affaibli. Ainsi, l'exécution de :

>>> for k in xrange(1000000): a[k] = k

causera :

MemoryError

Et similaire au "nombre magique" demandé:

>>> len(a)
87382