Quelle structure des données dois-je utiliser pour stocker des valeurs de hachage?

https://stackoverflow.com/questions/1957390

21-09-2019
|

Question

J'ai une table de hachage que je veux stocker sur le disque. La liste ressemble à ceci:

<16-byte key                   > <1-byte result>
a7b4903def8764941bac7485d97e4f76 04
b859de04f2f2ff76496879bda875aecf 03
etc...

Il y a 1-5 millions d'entrées. Actuellement, je suis juste de les stocker dans un fichier, 17-octets par temps d'entrée, le nombre d'entrées. Ce fichier est des dizaines de méga-octets. Mon but est de les stocker d'une manière qui optimise d'abord pour l'espace sur le disque, puis pour le temps de recherche. temps d'insertion est sans importance.

Quelle est la meilleure façon de le faire? Je voudrais que le fichier soit aussi faible que possible. Plusieurs fichiers seraient d'accord, aussi. Patricia Trie? Radix Trie?

Quelles que soient bonnes suggestions que je reçois, je vais mettre en œuvre et les tests. Je vais poster les résultats ici pour tout voir.

La solution

Vous pouvez simplement trier les entrées par clé et faire une recherche binaire.

touches de taille fixe et les entrées de données signifie que vous pouvez très rapidement sauter d'une ligne à et stocker uniquement la clé et des données signifie que vous n'êtes pas perdre de l'espace sur les méta-données.

Je ne pense pas que vous allez faire mieux sur l'espace disque, et les temps de recherche sont O (log (n)). temps d'insertion sont fous de temps, mais vous avez dit que ne pas d'importance.

Si vous êtes vraiment prêt à tolérer les temps d'accès longs, faire trier la table mais morceau en blocs d'une certaine taille et les compresser. Stocker le décalage * et démarrer / touches de fin de chaque bloc dans une section du fichier au début. En utilisant ce schéma, vous pouvez trouver le bloc contenant la clé dont vous avez besoin dans le temps linéaire, puis effectuez une recherche binaire dans le bloc décompressé. Choisissez le bloc dimensionnés en fonction de la quantité du fichier que vous êtes prêt à charger dans la mémoire à la fois.

L'utilisation d'un arrêt du système de compression de plateau (comme GZIP), vous pouvez régler le taux de compression selon les besoins; des fichiers plus volumineux seront probablement avoir plus rapidement les temps de recherche.

Je doute que les économies d'espace seront tous que les grands, comme la structure semble être la plupart du temps hash. Si elles sont hashs en fait, ils sont aléatoires et ne compresse pas terriblement bien. Tri aidera à augmenter le taux de compression, mais pas par une tonne.

_{* Utiliser l'en-tête pour rechercher le décalage d'un bloc à décompresser et à utiliser.}

Autres conseils

5 millions de disques, il est âgé d'environ 81MB - acceptables pour travailler avec tableau en mémoire.

Comme vous l'avez décrit problème - il est des clés plus uniques que les valeurs de hachage. Essayez d'utiliser la table de hachage pour accéder à des valeurs (consultez ce lien ).

S'il est mon mal comprendre, ce qui est vrai hachage -. Essayer de construire un deuxième au dessus du niveau de hachage de cette

table de hachage peut être organisé avec succès sur le disque trop (par exemple sous forme de fichier séparé).

Addition

Solution avec de bonnes performances de recherche et peu de frais généraux est:

Définir la fonction de hachage qui produit des valeurs entières à partir de touches.
Trier les enregistrements dans le fichier en fonction des valeurs, produites par cette fonction
décalages de fichiers de magasin où chaque valeur de hachage commence
Pour localiser la valeur:
4.1. le calculer de hachage avec la fonction
4.2. rechercher dans le fichier pour l'offset
4.3. lire les enregistrements de fichiers à partir de cette position jusqu'à ce que la clé trouvée ou décalage de clé suivante atteint ou non en fin de fichier.

Il y a des choses supplémentaires qui doivent être pointées sur:

fonction de hachage doit être rapide pour être efficace
Fonction de hachage doit produire des valeurs distribuées linéaires ou près de ce
Table des décalages de valeurs de hachage peut être placé dans le fichier séparé
Table des décalages de valeurs de hachage peut être produit de manière dynamique avec lecture séquentielle du fichier entier triés au début de l'application et stockées dans la mémoire
à l'étape 4.3. les dossiers doivent être readed par blocs, et non un par un, pour être efficace. lit idéal toutes les valeurs avec hachage calculée à la mémoire à la fois.

Vous pouvez trouver quelques exemples de fonctions de hachage .

Est-ce que le travail d'approche simple et de les stocker dans un base de données SQLite ? Je ne pense pas que ça va devenir une plus petite mais vous devriez obtenir de très bonnes performances de recherche, et il est très facile à mettre en œuvre.

D'abord - plusieurs fichiers ne sont pas OK si vous souhaitez optimiser l'espace disque, en raison de la taille de cluster - lorsque vous créez le fichier avec la taille ~ 100 octets, espaces disque diminue par taille de cluster - 2 Ko par exemple

En second lieu - dans votre cas, je stocker toutes les tables dans le fichier binaire unique, commandé simplement ASC par des valeurs octets dans les clés. Il déposera vous donner une longueur égale exactement à entriesNumber * 17, ce qui est minime si vous ne voulez pas utiliser l'archivage, et d'autre part, vous pouvez utiliser la recherche très rapide avec le temps ~ log2 (entriesNumber), lorsque vous recherchez le fichier clé de partage en deux parties et en comparant la clé de leur frontière avec la clé nécessaire. Si « clé de frontière » est plus grand, vous prenez la première partie du dossier, si plus - puis la deuxième partie. Et diviser à nouveau pris part en deux parties, etc. Donc, vous aurez besoin d'environ log2 (entriesNumber) opérations de lecture de clé de recherche unique.

Votre clé est de 128 bits, mais si vous avez max 10 ^ 7 entrées, il ne prend que 24 bits pour l'indexer.

Vous pouvez faire une table de hachage, ou
Utiliser le style Bentley recherche binaire déroula (au plus 24 comparaisons), comme dans

Voici la boucle déroulée (avec ints 32 bits).

int key[4];
int a[1<<24][4];

#define COMPARE(key, i) (key[0]>=a[i][0] && key[1]>=a[i][1] && key[2]>=a[i][2] && key[3]>=a[i][3])

i = 0;
if (COMPARE(key, (i+(1<<23))) >= 0) i += (1<<23);
if (COMPARE(key, (i+(1<<22))) >= 0) i += (1<<22);
if (COMPARE(key, (i+(1<<21))) >= 0) i += (1<<21);
...
if (COMPARE(key, (i+(1<<3))) >= 0) i += (1<<3);
if (COMPARE(key, (i+(1<<2))) >= 0) i += (1<<2);
if (COMPARE(key, (i+(1<<1))) >= 0) i += (1<<3);

Comme toujours avec la conception de fichiers, plus vous savez (et nous dire) au sujet de la distribution des données mieux. En supposant que vos valeurs clés sont uniformément réparties sur l'ensemble de toutes les clés de 16 octets - qui devrait être vrai si vous stockez une table de hachage - Je suggère une combinaison de ce que d'autres ont déjà suggéré:

données binaires comme cela appartient à un fichier binaire; ne laissez pas le fait que la représentation facile de vos hash et les valeurs sont comme des chaînes de chiffres hexadécimaux vous tromper en pensant que ce sont les données de chaîne;
taille du fichier est telle que tout le tralala peut être conservé en mémoire sur un PC ou d'un serveur moderne et beaucoup d'autres dispositifs aussi;
principaux 4 octets de clés divisent l'ensemble des clés possibles en 16 ^ 4 (= 65536) des sous-ensembles; si vos clés sont réparties uniformément et vous avez 5x10 ^ 6 entrées, soit environ 76 entrées par sous-ensemble; afin de créer un fichier avec un espace pour, disons, 100 entrées par sous-ensemble; puis:
à l'offset 0 commencer à écrire toutes les entrées avec les principaux 4 octets 0x0000; tampon au total de 100 entrées (1700 octets je crois) avec 0s;
à l'offset 1700 commencer à écrire toutes les entrées avec les principaux 4 octets 0x0001, pad,
répétition jusqu'à ce que vous avez écrit toutes les données.

Maintenant, votre recherche devient un calcul pour déterminer le décalage dans le fichier suivie d'une analyse jusqu'à 100 entrées pour trouver celui que vous voulez. Si cela ne suffit pas rapide puis utilisez 16 ^ 5 sous-ensembles, ce qui permet environ 6 entrées par sous-ensemble (6x16 ^ 5 = 6291456). Je suppose que ce sera plus rapide que la recherche binaire - mais il est qu'une supposition

L'insertion est un peu un problème, il est à vous avec vos connaissances de vos données pour décider si de nouvelles entrées (a) nécessitent la re-tri d'un sous-ensemble ou (b) peut simplement être ajouté à la fin de la liste des entrées à cet index (ce qui signifie que le balayage du sous-ensemble complet sur chaque consultation).

Si l'espace est très important que vous pouvez, bien sûr, laisser tomber les principaux 4 octets de vos entrées, car ils sont calculés par le calcul du décalage dans le fichier.

Ce que je décris, pas très bien, est un table de hachage .

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow