Mémoire efficace chaîne à chaîne carte en Python (ou C)

StackOverflow https://stackoverflow.com/questions/4026359

Question

J'ai besoin d'une structure de données efficace mémoire pour pour stocker environ un million de paires clé - valeur, où les clés sont des chaînes d'environ 80 octets, et les valeurs sont des chaînes d'environ 200 octets, la taille de la clé et la valeur totale étant d'environ 280MB . Je dois aussi recherche efficace de la valeur par clé, de préférence un hachage carte. La surcharge de la mémoire doit être aussi peu que possible, par exemple pour 280MB de données utiles, la structure de données ne doit pas utiliser plus de 300 Mo de mémoire virtuelle (y compris les frais généraux de malloc() et tout le reste). Le modèle d'utilisation est la suivante: nous commençons par une structure de données vide, et nous remplissons il change peu à peu, jamais les clés, et ne jamais changer la longueur des valeurs. En plus, la structure de données peut prendre en charge la modification de la longueur des valeurs, au détriment d'une surcharge de la valeur de 100% (ce qui signifie que pour x octets de valeur, x octets pourrait être perdu dans temporairement dans l'espace de mémoire tampon inutilisé).

I besoin d'un module python pur, ou un module Python intégré, ou une mise en oeuvre de préférence avec C (C) des liaisons python. Je préférerais que l'on pouvait sérialiser l'ensemble de la structure de données sur le disque, et relis très rapidement.

Juste pour prouver qu'une telle petite surcharge est possible, j'ai créé un design simple avec adressage ouvert , la table de hachage de 1,25 million d'éléments contenant des pointeurs de 4 octets de blocs de données 1MB, les blocs de données contenant les longueurs de clés et de valeurs comme base 128 varints . Cette conception a une limitation importante: il ne permet pas supprimer ou modifier des paires sans perdre de leur zone de mémoire. Selon mes calculs avec 1 million de paires clé - valeur de 280 octets chacune, la tête est inférieure à 3,6% (10 080 000 octets). Les limites ci-dessus sont plus généreux, ils permettent 20 000 000 octets de frais généraux.

Je viens de trouver http://www.pytables.org/ , qui offre un accès rapide et emballage économe en mémoire des données. Je dois l'examiner de plus près pour vérifier si elle convient à mes besoins.

Était-ce utile?

La solution 10

Depuis que je ne pouvais pas trouver des solutions existantes qui emballera la mémoire bien, je l'ai décidé de le mettre en œuvre en C pour moi-même. Voir ma conception avec l'adressage ouvert dans la question.

Autres conseils

Ok, l'approche de saleté simple.

Utilisez un dictionnaire python pour la structure de données. Je remplissais un dictionnaire python avec 1 million de paires clé-valeur au hasard où la clé était de 80 caractères et la valeur 200 caractères. Il a fallu 360844 Kb sur mon ordinateur, ce qui est en dehors de votre cahier des charges de plus de 300 Mo, mais je l'offre comme une solution de toute façon car il est encore assez efficace de la mémoire.

échoue également votre condition d'avoir une API C. Je ne sais pas pourquoi vous avez besoin C, mais la question est marqué Python et manque une étiquette C, je vais offrir le pur Python pour voir si elle pourrait bien faire l'affaire.

En ce qui concerne la persistance. Utilisez le module cPickle. Il est très rapide et, encore une fois, saleté simple. Pour enregistrer votre dictionnaire: 

cPickle.dump(mydict, "myfile.pkl")

Pour recharger votre dictionnaire: 

mydict = cPickle.load("myfile.pkl")

Une seconde idée de saleté simple est d'utiliser le module shelve, qui est essentiellement le dictionnaire python sur disque. les frais généraux de la mémoire est très faible (il est tout sur le disque). Mais il est aussi beaucoup plus lent.

Martijn a mentionné dans un commentaire (ne sais pas pourquoi les gens commentaires des réponses), mais je suis d'accord: utiliser SQLite. Vous devriez essayer et voir si elle répondra à vos besoins.

Si vous ne prévoyez pas d'avoir une grande quantité de suppressions, alors ce n'est pas difficile. Supprime conduisent à une fragmentation.

Vous devez également engager à une clé de longueur fixe. Vous avez parlé de 80 octets. Vos clés autorisés à reproduire? Sinon, il est encore plus facile.

Alors, voici ce que vous faites.

Vous créez un tableau de: 

struct {
    char value[80];
    char *data;
} key;

Et vous gardez ce tableau triée.

Si vous pouvez dupliquer les clés, vous devez: 

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

(Mon C est rouillé, mais c'est l'essentiel de celui-ci) Ce dernier a chaque pointage clé d'une liste chaînée des valeurs.

Ensuite, une recherche est une simple recherche binaire. La « douleur » est dans le maintien de ce tableau et l'insertion / suppression de clés. Ce n'est pas aussi douloureux que cela puisse paraître, mais il permet d'économiser beaucoup de mémoire, en particulier sur les systèmes 64 bits.

Qu'est-ce que vous voulez réduire le nombre de pointeurs. Pointeurs sont chers quand vous avez beaucoup de structures remplies de pointeurs. Sur un système 64 bits, un pointeur est de 8 octets. Donc, pour un seul pointeur, il en va de 8MB de votre budget mémoire.

Ainsi, la dépense est dans la construction du tableau, la copie et la mémoire de compactage (si vous « savez » que vous aurez un million de lignes et peut engager à cela, alors malloc (1000000 * sizeof (clé)) tout de suite, ce ll vous faire économiser de la copie lors de l'expansion).

Mais ne craignez pas, une fois qu'il est opérationnel, la performance est assez bonne. CPUs modernes sont en fait assez bon à copier 100M blocs de mémoire autour.

En passant, je viens de faire quelque chose de beaucoup comme celui-ci en Java. Sur une machine virtuelle Java 64 bits, une carte avec des entrées de 25M est 2G de RAM. Ma solution (en utilisant des techniques similaires à ce sujet) a à environ 600 m). Java utilise plus de pointeurs que C, mais le principe est le même.

Avez-vous essayé d'utiliser un dict simple? La plupart de vos données est dans les chaînes, de sorte que les frais généraux pourrait satisfaire à vos besoins.

Vous pouvez utiliser la sha1 de la clé au lieu de la clé elle-même. Si les touches sont uniques, le hachage sha1 des clés est probable aussi. Il fournit une économie de mémoire pour essayer de Squeak sous votre limite. 

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

Sur ma boîte ubuntu, ce plafonne à 304 Mo de mémoire: 

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

Assez proche? Ce python de non C.

Plus tard: aussi, si vos données sont quelque peu redondante, vous pouvez gzip les valeurs. Il est un temps par rapport à l'espace compromis.

En utilisant SQLite est une bonne idée. Une mise en œuvre rapide peut dire si vous êtes assez rapide avec peu d'effort.

Si vous déterminez vous devez rouler votre propre, je recommande ce qui suit:

Dans quelle mesure pouvez-vous prédire le nombre de paires, ou une limite supérieure pour cela?
Dans quelle mesure pouvez-vous prédire la taille totale des données, ou une limite supérieure pour cela?

Arena allocateur pour les chaînes et les nœuds. (En règle générale, vous souhaitez travailler sur une liste d'arènes, de sorte que vous n'avez pas de prédire la taille totale).

L'alignement dépend de vos algorithmes, en principe, vous pouvez emballer un octet serré, et la seule tête est votre surutilisation, qui ne touche que très peu votre jeu de travail.

Toutefois, si vous devez exécuter un cmp / copier etc. opérations sur ces cordes, rappelez-vous que les garanties suivantes, vous pouvez presser un peu ou beaucoup de ces opérations de chaîne:

  • tous les éléments sont alignés mot de CPU
  • tous les octets de remplissage sont (par exemple) 0
  • vous pouvez lire en toute sécurité « au-delà » une fin de chaîne aussi longtemps que vous ne traversez pas une frontière CPU

table de Hash pour l'indice. Un dictionnaire fonctionnerait aussi, mais qui n'a de sens que si la dégradation potentielle / ressasser serait un grave problème. Je ne sais pas « stock » la mise en œuvre Hashtable C, mais il devrait y avoir un, non? droite? Il suffit de remplacer les allocations par des appels à l'allocateur arène.

Mémoire Localité

Si vous pouvez garantir que recherche ne demandera jamais une chaîne qui ne sont pas sur la carte, vous devez stocker les clés dans une arène séparée, car ils ne sont nécessaires que sur les collisions de hachage. Cela peut améliorer considérablement la localisation de mémoire. (Dans ce cas, si jamais vous avez une table « finale », vous pouvez même copier les clés qui entrent en collision à une nouvelle arène, et jeter tous les autres. Les avantages qui en découlent sont probablement marginal, cependant.)

La séparation peut aider ou mal, selon vos habitudes d'accès. Si vous utilisez généralement la valeur une fois après chaque recherche, les ayant par paires dans la même arène est grande. Si vous par exemple rechercher quelques clés, utilisez leurs valeurs à plusieurs reprises, arènes distinctes sens.

Si vous devez soutenir « drôles de personnages » / Unicode, normaliser vos chaînes avant de les stocker.

Vous pouvez utiliser le module struct pour emballer des données binaires et décompresser en cas de besoin. Vous pouvez mettre en place un stockage efficace de la mémoire en utilisant cette approche. Je suppose que l'accès serait une douleur.

Apache Portable Runtime (aka APR) a une table de hachage à base c. Vous pouvez consulter la documentation http://apr.apache.org/docs/apr/ 0,9 / group_ avril _hash.html

Avec tout ce que vous stockez apr_hash_t est vide *. Ainsi, il vous donne un contrôle total sur les valeurs. Donc, si vous voulez, vous pouvez stocker le pointeur sur un bloc de 100 octets au lieu de la longueur réelle de la chaîne.

Judy doit être économe en mémoire: http://judy.sourceforge.net/
(Critères de référence: http://www.nothings.org/computer/judy/ , voir " Structure de données Taille ").
Voir aussi: http://www.dalkescientific.com/Python/PyJudy.html

En outre,

Pour les clés d'une taille fixe, il est http://panthema.net/2007/stx-btree / en C ++ (je suis sûr que, avec des emballages C personnalisés il peut être utilisé à partir CPython). Si l'ensemble de données permet, vous pouvez stocker les clés de longueur variable de la valeur et d'utiliser un hachage ou un préfixe de la clé de longueur variable comme la clé de longueur fixe.

La même logique applique à http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-and-time.html et http://code.google.com/p/sparsehash/ - istead d'utiliser un std :: string lourd comme une clé, utilisez un 32 bits ou la clé de nombre entier de 64 bits, ce qui en fait en quelque sorte de la vraie clé de longueur variable.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top