Choix d'une structure de données pour des données très volumineuses

Question

J'ai des x (millions) entiers positifs, où leurs valeurs peuvent être aussi grandes que permises (+2 147 483 647). En supposant qu'ils sont uniques, quelle est la meilleure façon de les stocker pour un programme intensif de recherche. Jusqu'à présent, j'ai pensé à utiliser une arborescence AVL binaire ou une table de hachage, où l'entier est la clé des données mappées (un nom). Cependant suis pas sûr que je peux mettre en œuvre ces grandes touches et en si grande quantité avec une table de hachage (ne serait-ce créer un> 0,8 facteur de charge en plus d'être sujettes à des collisions?)

Puis-je obtenir quelques conseils sur quelle structure de données pourrait convenir à ma situation

Answer 1

Le choix de la structure dépend fortement de la quantité de mémoire disponible. Je suppose en fonction de la description que vous avez besoin de recherche, mais pas de boucle sur eux, trouver le plus proche, ou d'autres opérations similaires.

Meilleur est probablement une table de hachage seau. En plaçant des collisions de hachage dans des compartiments et en conservant des baies distinctes dans le compartiment pour les clés et les valeurs, vous pouvez réduire la taille de la table et tirer parti de l'accélération du cache de l'UC lors de la recherche dans un compartiment. La recherche linéaire dans un compartiment peut même finir plus rapidement que la recherche binaire! Les arborescences AVL sont utiles pour les ensembles de données lues en lecture mais pas en lecture seule ET nécessitent une énumération ordonnée, la recherche des opérations les plus proches et similaires, mais leur implémentation est fastidieuse. Vous pouvez obtenir de meilleures performances avec un B-tree en raison du comportement du cache de l'UC, en particulier un algorithme B-tree insensible au cache.

Answer 2

Avez-vous examiné les arbres B? L'efficacité passe entre log_m(n) et log_(m/2)(n) donc si vous choisissez m être autour de 8-10 ou vous devriez donc être en mesure de garder votre profondeur de recherche ci-dessous 10.

Answer 3

Si la mémoire est pas un problème une carte est probablement votre meilleur pari. Les cartes sont O (1) ce qui signifie que si vous augmentez le nombre d'éléments à rechercher, le temps nécessaire pour trouver une valeur est le même.

Une carte où la clé est int, et la valeur est le nom.

Answer 4

Essayez d'abord les tables de hachage. Certaines variantes peuvent tolérer être très denses sans ralentissement significatif (comme la variation de Brent).

Si vous avez uniquement besoin de stocker les entiers 32 bits et aucun enregistrement associé, utilisez un set et non un map, comme hash_set dans la plupart des bibliothèques C++. Il n'utiliserait que des enregistrements de 4 octets plus des frais généraux constants et un peu de marge pour éviter d'être à 100%. Dans le pire des cas, pour gérer des «millions» de chiffres, vous aurez besoin de quelques dizaines de mégaoctets. Gros, mais rien d'ingérable.

Si vous avez besoin d'être beaucoup plus serré, il suffit de les stocker triés dans un tableau simple et d'utiliser la recherche binaire pour les récupérer. Ce sera O (log n) au lieu de O (1), mais pour des millions d'enregistrements, il ne reste que vingt étapes pour obtenir l'un d'entre eux. En C vous avez bsearch(), qui est aussi rapide que possible.

éditer: juste vu dans votre question vous parlez de quelques 'données mappées (un nom)'. ces noms sont-ils uniques? doivent-ils aussi être en mémoire? Si oui, ils domineraient certainement les exigences de mémoire. Même ainsi, si les noms sont les mots anglais typiques, la plupart seraient de 10 octets ou moins, gardant la taille totale dans les «dizaines de mégaoctets»; peut-être jusqu'à une centaine de megs, toujours très maniable.

Answer 5

Bit Vecteur, avec l'index défini si le nombre est présent. Vous pouvez le modifier pour avoir le nombre d'occurrences de chaque nombre. Il y a une belle colonne sur les vecteurs binaires dans les Perles de programmation de Bentley.