Le choix d'une structure de données pour les données très importantes

Question

Je x (en millions) d'entiers positifs, où leurs valeurs peuvent être aussi grand que permis (2147483647). En supposant qu'ils sont uniques, quelle est la meilleure façon de les stocker pour un programme intensif de recherche.

Jusqu'à présent, je pensais à l'aide d'un arbre AVL binaire ou une table de hachage, où l'entier est la clé des données cartographiées (un nom). Cependant je ne suis pas sûr que pour que je puisse mettre en œuvre ces grandes touches et en si grande quantité avec une table de hachage (ne que créer un> 0,8 facteur de charge en plus d'être sujettes à des collisions?)

Puis-je obtenir quelques conseils sur lequel la structure de données peut convenir à ma situation

Answer 1

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

Le meilleur est probablement une table de hachage bucketed. En plaçant les collisions de hachage dans des seaux et de garder des tableaux séparés dans le seau pour les clés et les valeurs, vous pouvez à la fois réduire la taille de la table appropriée et tirer parti de cache CPU speedup lors de la recherche d'un seau. La recherche linéaire dans un godet peut même finir plus vite que la recherche binaire!

AVL sont bien pour les ensembles de données qui sont en lecture intensive mais pas en lecture seule et nécessitent le dénombrement ordonné, trouver les plus proches et les opérations similaires, mais ils sont une quantité agaçante de travail à mettre en œuvre correctement. Vous pouvez obtenir de meilleures performances avec un B-tree en raison du comportement du cache du processeur, bien que, en particulier un cache inconscient algorithme B-tree.

Answer 2

Avez-vous regardé dans B-arbres? Les pistes d'efficacité entre log_m(n) et log_(m/2)(n) donc si vous choisissez d'être m autour de 8-10 ou de sorte que vous devriez être en mesure de garder votre profondeur de recherche à moins de 10.

Answer 3

Bit Vector, avec l'ensemble d'indices si le nombre est présent. Vous pouvez modifier à avoir le nombre d'occurrences de chaque numéro. Il y a une colonne bien sur les vecteurs de bits dans les perles de programmation de Bentley.

Answer 4

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 comme vous l'échelle le nombre d'articles à regardé le temps nécessaire pour trouver une valeur est le même.

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

Answer 5

Bougez tables de hachage d'abord essayer. Il y a quelques variantes qui peuvent tolérer d'être très dense sans ralentissement significatif (comme la variation de Brent).

Si vous avez seulement besoin de stocker les entiers de 32 bits et pas enregistrer les associés, utilisez un set et non un map, comme dans la plupart des bibliothèques hash_set C ++. Il utiliserait seulement 4 octets dossiers ainsi que certains frais généraux constant et un peu de mou pour éviter d'être 100%. Dans le pire des cas, pour traiter « millions » de chiffres que vous auriez besoin de quelques dizaines de méga-octets. Big, mais rien impossible à gérer.

Si vous avez besoin d'être beaucoup plus serré, il suffit de les stocker triés dans un tableau simple et utiliser la recherche binaire pour aller les chercher. Il sera O (log n) au lieu de O (1), mais pour « millions » de dossiers, il est encore juste twentysomething étapes pour obtenir l'un d'eux. En C, vous avez bsearch(), qui est aussi vite qu'il peut obtenir.

modifier : juste vu dans votre question, vous parlez des «données cartographiées (un nom). sont les noms uniques? ils doivent aussi être en mémoire? si oui, ils dominent nettement les besoins en mémoire. Cependant, si les noms sont les mots anglais typiques, la plupart serait de 10 octets ou moins, en gardant la taille totale des « dizaines de méga-octets »; peut-être jusqu'à une centaine de mégas, toujours très facile à gérer.