Le choix d'une structure de Données pour les données très volumineux
J'ai x (millions de dollars) d'entiers positifs, où leurs valeurs peuvent être aussi gros que autorisées (+de 2 147 483 647). En supposant qu'ils sont uniques, quelle est la meilleure façon de les conserver pour un programme intensif de recherche.
Jusqu'à présent j'ai pensé à utiliser un binaire AVL arbre ou une table de hachage, où le nombre entier est la clé de données cartographiées (un nom). Cependant je ne suis pas sûr de savoir si je peut mettre en œuvre ces grandes touches et en si grande quantité avec une table de hachage (ne serait-ce pas créer un >0.8 facteur de charge de plus être sujettes à des collisions?)
Pourrais-je avoir quelques conseils sur la structure de données qui pourrait être adapté à ma situation
Ligne de cache du PROCESSEUR remplit peut avoir le même effet sur les performances de la base de données page lit le faire, mais à la microseconde plutôt qu'à l'échelle de la milliseconde.
si vous allez utiliser un Auto-Équilibrage de l'Arbre alors je vous recommande fortement de lire cet article: web.stanford.edu/~blp/documents/libavl.pdf
OriginalL'auteur Carlos | 2010-11-24
Vous devez vous connecter pour publier un commentaire.
Le choix de la structure dépend fortement de la quantité de mémoire disponible. Je suppose d'après la description que vous avez besoin de recherche, mais pas en boucle, trouver le plus proche, ou d'autres opérations similaires.
Le mieux est probablement placées dans un compartiment de la table de hachage. En plaçant les collisions de hachage dans des seaux, et en gardant tableaux distincts dans le seau pour les clés et les valeurs, vous pouvez à la fois de réduire la taille de la table appropriée et de prendre avantage de cache du PROCESSEUR de l'accélération lors de la recherche d'un seau. La recherche linéaire dans un seau peut même finir plus vite que les binaires de recherche!
AVL arbres sont sympas pour les jeux de données de lecture intensive, mais pas en lecture seule ET nécessitent commandé énumération, trouver le plus proche et d'autres opérations similaires, mais ils sont un fâcheusement quantité de travail à mettre en œuvre correctement. Vous pouvez obtenir les meilleures performances avec un B-arbre à cause de la cache du PROCESSEUR comportement, mais, surtout, un cache-inconscient B-algorithme d'arbre.
OriginalL'auteur Jeffrey Hantin
Avez-vous regardé dans les B-arbres? L'efficacité s'étend entre
log_m(n)
etlog_(m/2)(n)
donc, si vous choisissezm
être autour de 8-10 ou si vous devez être en mesure de garder votre recherche de profondeur au-dessous de 10.m
être autour de 8 à 10 au lieu den
?Bon, désolé, mon mauvais.
OriginalL'auteur Actorclavilis
Vecteur de bits , avec l'index de définir si le numéro est présent. Vous pouvez modifier le nombre d'occurrences de chaque numéro. Il y a une belle chronique sur les vecteurs de bits dans la Bentley de Programmation de Perles.
OriginalL'auteur gsb
Si la mémoire n'est pas un problème, une carte est probablement votre meilleur pari. Les cartes sont en O(1) ce qui signifie que que vous évoluer le nombre d'éléments à être regardé, le temps est nécessaire pour trouver une valeur est la même.
Une carte où la clé est de type int, et la valeur est le nom.
Oh bien sûr, il faudrait une tonne de mémoire. Mais j'ai fait de qualifier cette déclaration avec un "Si la mémoire n'est pas un problème"... juste une idée.
comment puis-je calculer la quantité de mémoire que j'ai besoin, dans ce cas, la quantité de mémoire de votre mise. Est-il de toute façon à calculer?
Par carte voulez-vous dire certains (variante) bitvector (dans ce cas)? Je ne peux pas vraiment penser à toute autre garantie O(1) de la structure. Plus précisément, pas une carte tel que mis en œuvre par un arbre.
une carte, c'est tout simplement quelque chose avec une clé et un enregistrement. même un linéaire de recherche liste est conforme. vous parle probablement d'une table de hachage, ou "hash map" comme on le sait sur certaines bibliothèques.
OriginalL'auteur Michael Peddicord
Faire essayer les tables de hachage en premier. Il y a quelques variantes qui peuvent tolérer d'être très dense sans ralentissement considérable (comme le Brent de la variation).
Si vous avez seulement besoin de stocker les nombres entiers de 32 bits et non pas un enregistrement associé, utiliser un
set
et pas unmap
, commehash_set
dans la plupart des bibliothèques C++. Elle serait d'utiliser seulement 4 octets de dossiers en plus de certains constant de charge et d'un peu de mou pour éviter d'être à 100%. Dans le pire des cas, à gérer "des millions" de numéros, vous auriez besoin de quelques dizaines de méga-octets. Grand, mais rien d'ingérable.Si vous en avez besoin pour être beaucoup plus serré, juste de les stocker triés dans un simple tableau et utiliser les binaires de recherche pour les récupérer. Il sera en O(log n) au lieu de O(1), mais pour les "millions" de dossiers, il est encore tout jeune étapes pour obtenir un quelconque d'entre eux. En C, vous avez
bsearch()
, qui est aussi vite qu'elle peut obtenir.modifier: viens de voir dans votre question, vous parlez de certains " données cartographiées (nom)'. sont ces noms uniques? ils doivent également être en mémoire? si oui, ils auraient certainement dominer les besoins en mémoire. De même, si les noms sont typiques des mots anglais, plus de 10 octets ou moins, en gardant la taille totale dans les "dizaines de méga-octets'; peut-être jusqu'à une centaine de mo, toujours très maniable.
OriginalL'auteur Javier