Consommation de mémoire Python: dict VS liste de tuples

Il y a beaucoup de questions et de discussion à propos de la consommation de mémoire des différents python les types de données. Pourtant, peu d'entre eux (le cas échéant) d'arriver à un scénario très spécifique. Lorsque vous souhaitez stocker BEAUCOUP de données clé-valeur dans la mémoire, des données dont la structure est plus efficace de la mémoire, une dict ou une liste de tuples?

Au début je pensais que dict est plus puissant que la liste de tuples et que le pouvoir doit venir avec un certain prix, et en fait un vide dict NE s'occupent plus de mémoire qu'une liste vide ou n-uplet (voir En mémoire de la taille d'un Python de la structure), donc j'ai pensé à l'aide de [(key1, value1), (key2, value2), ...] serait plus efficace de la mémoire que {key1: value1, key2: value2, ...}.

Semble que j'ai été mauvais. Lancez simplement l'extrait de code suivant, et de voir le mem consommation rapporté par votre système d'exploitation. Je suis avec Windows XP ainsi que le gestionnaire des tâches m'indique, un grand dict mange "seulement" 40 MO de Ram et 40 mo VIRTURAL de Ram, mais une liste de tuples mange jusqu'à 60 mo de Ram et 60 MO ram Virtuelle.

Comment pourrait-ce être?

from sys import getsizeof as g
raw_input('ready, press ENTER')
i = 1000000
#p = [(x, x) for x in xrange(i)] # Will print 4,348,736 40,348,736
p = dict((x, x) for x in xrange(i)) # Will print 25,165,964 37,165,964
print g(p), g(p) + sum(g(x) for x in p)
raw_input("Check your process's memory consumption now, press ENTER to exit")

Mise à jour:

Merci pour les quelques commentaires ci-dessous. Je veux préciser: je parle de la mémoire de l'efficacité. Et non, dans ce cas, pas besoin de vous inquiéter de la valeur-clé de recherche d'efficacité, nous allons simplement supposer que mon algorithme va consommer un par un via un itérateur.

source d'informationauteur RayLuo | 2013-03-26

  1. 20

    Votre list de tuples ajoute une couche supplémentaire. Vous avez 3 couches d'éléments:

    • La liste externe de longueur 1 m, donc 1 million de pointeurs
      • 1 m 2 de logement de tuples, donc 2 millions de pointeurs
        • 2 millions de références à 1 million de valeurs entières

    pendant que votre dict ne détient:

    • Le dict (y compris 1 m en cache de hachages) avec 2 millions de pointeurs + espace supplémentaire pour pousser la table
      • 2 millions de références à 1 million de valeurs entières

    C'est ces 1 millions de tuples en plus de la liste de tenir les références que prendre plus de mémoire que le 1 million de mises en cache les valeurs de hachage. Il y a quelques 50% de plus de pointeurs ici, facilement comptables pour les 50% de plus que l'utilisation de la mémoire vous voir.

    Il y a un autre inconvénient à votre liste de tuples: recherche de temps. Pour trouver une clé correspondante dans le dict, il est un O(1) coût de complexité. Pour faire de même dans la liste de tuples, vous avez potentiellement de numériser l'ensemble de la liste pour un O(n) le coût. Ne pas utiliser une liste de tuples si vous avez besoin de mapper les touches de valeurs.

  2. 7

    Vous êtes réellement obtenir une image incomplète de l'utilisation de la mémoire dans ce cas. La taille totale d'un dictionnaire de plus du double à intervalles irréguliers, et si vous comparez la taille de ces deux structures à droite après le dictionnaire de plus grande taille, il est plus grand encore. Un script simple avec récursive en fonction de la taille (voir le code ci-dessous) montre une assez clair motif:

    i:  2  list size:  296  dict size:  328  difference:  -32
i:  3  list size:  392  dict size:  352  difference:  40
i:  4  list size:  488  dict size:  376  difference:  112
i:  5  list size:  616  dict size:  400  difference:  216
i:  7  list size:  808  dict size:  1216  difference:  -408
i:  10  list size:  1160  dict size:  1288  difference:  -128
i:  13  list size:  1448  dict size:  1360  difference:  88
i:  17  list size:  1904  dict size:  1456  difference:  448
i:  23  list size:  2480  dict size:  3904  difference:  -1424
i:  31  list size:  3328  dict size:  4096  difference:  -768
i:  42  list size:  4472  dict size:  4360  difference:  112
i:  56  list size:  5912  dict size:  4696  difference:  1216
i:  74  list size:  7880  dict size:  5128  difference:  2752
i:  100  list size:  10520  dict size:  14968  difference:  -4448
i:  133  list size:  14024  dict size:  15760  difference:  -1736
i:  177  list size:  18672  dict size:  16816  difference:  1856

    Cette tendance se poursuit i grandit. (Vous pouvez le tester à l'aide de votre méthode, essayez de définir i près de 2636744. La taille du dictionnaire est plus grande à ce point, au moins pour moi.) Martijn est un droit que le n-uplets dans la liste de tuples ajouter à la surcharge de la mémoire, l'annulation de la mémoire de l'avantage des listes sur les dictionnaires. Mais le résultat, en moyenne, n'est pas que le dictionnaire est mieux; c'est que le dictionnaire est la même. Donc, en réponse à votre question de départ:

    Lorsque vous souhaitez stocker BEAUCOUP de données clé-valeur dans la mémoire, des données dont la structure est plus efficace de la mémoire, une dict ou une liste de tuples?

    Il n'a pas vraiment d'importance si vous êtes inquiète, c'est la mémoire.

    Cependantnote que de parcourir un dictionnaire est souvent un peu plus lent que d'itérer sur une liste, car il n'y a pas de bonne façon d'éviter l'itération sur toutes les cellules vides dans le dictionnaire. Donc, il y a un peu un compromis -- dictionnaires sont (beaucoup) plus rapide à faire clé aléatoire recherches, mais les listes sont (un peu) plus rapide à l'itération. Le dictionnaire sera probablement mieux la plupart du temps, mais dans certains cas rares, la liste peut fournir un micro-optimisation.

    Voici le code qui teste pour la taille. Il ne sera probablement pas générer des résultats corrects pour tous les cas de coin, mais il doit gérer des structures simples comme ça, sans aucun problème. (Mais laissez-moi savoir si vous voyez des problèmes.) 

    import sys, collections, itertools, math

def totalsize(x):
    seen = set()
    return ts_rec(x, seen)

def ts_rec(x, seen):
    if id(x) in seen:
        return 0
    else:
        seen.add(id(x))

    x_size = sys.getsizeof(x)
    if isinstance(x, collections.Mapping):
        kv_chain = itertools.chain.from_iterable(x.iteritems())
        return x_size + sum(ts_rec(i, seen) for i in kv_chain)
    elif isinstance(x, collections.Sequence):
        return x_size + sum(ts_rec(i, seen) for i in x)
    else:
        return x_size

for i in (10 ** (e / 8.0) for e in range(3, 19)):
    i = int(i)
    lsize = totalsize([(x, x) for x in xrange(i)])
    dsize = totalsize(dict((x, x) for x in xrange(i)))

    print "i: ", i,
    print " list size: ", lsize, " dict size: ", dsize,
    print " difference: ", lsize - dsize