J'ai des entiers positifs x (millions), où leurs valeurs peuvent être aussi grandes que celles autorisées (+2 147 483 647). En supposant qu'ils soient uniques, quelle est la meilleure façon de les stocker pour un programme intensif de recherche.
Jusqu'à présent, j'ai pensé à utiliser un arbre AVL binaire ou une table de hachage, où l'entier est la clé des données mappées (un nom). Cependant, je ne suis pas sûr de savoir si je peux mettre en œuvre de telles grandes clés et dans une telle grande quantité avec une table de hachage (ne créerait pas de> 0,8 facteur de charge en plus d'être sujette aux collisions?)
Pourrais-je obtenir des conseils sur quelle structure de données pourrait convenir à ma situation
5 Réponses :
Avez-vous regardé dans des arbres B? L'efficacité fonctionne entre log_m (n) et log_ (m / 2) (n) donc si vous choisissez m pour être autour de 8-10 Vous devriez donc être capable de garder votre profondeur de recherche à moins de 10 ans.
ne devrait-il pas choisir m d'être environ 8-10 au lieu de n ?
Si la mémoire n'est pas un problème, une carte est probablement votre meilleure mise. Les cartes sont O (1) signifiant que lorsque vous accumulez le nombre d'éléments à rechercher, le temps est nécessaire pour trouver une valeur est la même.
Une carte où la clé est l'INT, et la valeur est le nom.
Ne pas être impoli ou quoi que ce soit, mais comme je suppose que sa table est clairsemée, cela n'aurait-il pas besoin d'une quantité de mémoire ridicule?
Oh certainement, cela prendrait une tonne de mémoire. Mais j'ai qualifié cette déclaration avec une "si la mémoire n'est pas un problème" ... juste une idée.
Comment puis-je calculer la quantité de mémoire dont j'aurai besoin, dans ce cas, quelle quantité de mémoire sera votre implémentation. Y a-t-il de toute façon pour calculer cela?
Par carte, vous voulez dire quelque (variante sur) Bitvector (dans ce cas)? Je ne peux pas vraiment penser à une autre structure garantie O (1). Spécifiquement, pas une carte comme mise en œuvre par un arbre.
Une carte signifie juste quelque chose avec une clé et un enregistrement. Même une liste à la recherche de manière linéaire est conforme. Vous parlez probablement d'une table de hachage ou d'une "carte de hachage", comme sur certaines bibliothèques.
Le choix de la structure dépend fortement de la quantité de mémoire disponible. Je suppose que sur la description de la description dont vous avez besoin de rechercher, mais de ne pas boucler sur eux, de trouver des opérations les plus proches ou d'autres opérations similaires.
meilleur est probablement une table de hachage à seau. En plaçant des collisions de hasch dans des seaux et en gardant des matrices séparées dans le seau pour clés et valeurs, vous pouvez réduire la taille de la table appropriée et tirer parti de la vitesse de cache CPU lors de la recherche d'un godet. La recherche linéaire dans un godet peut même se retrouver plus rapidement que la recherche binaire!
Les arbres AVL sont agréables pour les ensembles de données qui sont en lecture seule mais non en lecture seule et nécessitent une énumération ordonnée, trouvent des opérations les plus proches et similaires, mais elles sont une quantité ennuyeuse de travail à mettre en œuvre correctement. Vous pouvez obtenir une meilleure performance avec un arbre B à cause du comportement de cache de la CPU, cependant, en particulier un algorithme B-Tree B-Tree de cache.
Essayez d'abord les tables de hasch. Certaines variantes peuvent tolérer d'être très dense sans ralentissement significatif (comme la variation de Brent).
Si vous n'avez besoin que de stocker les entiers 32 bits et non d'un enregistrement associé, utilisez un Si vous en avez besoin pour être beaucoup plus serré, rangez-les simplement dans un tableau uni et utilisez une recherche binaire pour les chercher. Ce sera O (log n) au lieu de O (1), mais pour «des millions de documents», il n'est toujours que des étapes pour obtenir l'un d'entre eux. Dans C, vous avez EDIT : vient de voir dans votre question que vous parlez de certaines données mappées (un nom) '. Ces noms sont-ils uniques? Est-ce qu'ils doivent aussi être en mémoire? Si oui, ils domineraient certainement les exigences de la mémoire. Malgré tout, si les noms sont les mots anglais typiques, la plupart dureraient 10 octets ou moins, en gardant la taille totale dans les "dizaines de mégaoctets"; Peut-être jusqu'à cent mégots, toujours très gérables. définir et non une carte , 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 mou pour éviter d'être 100%. Dans le pire des cas, pour gérer des «millions» de chiffres, vous auriez besoin de quelques dizaines de mégaoctets. Grosse, mais rien de non mangeable.
bSearch () , qui est aussi rapide que possible.
Vecteur de bit, avec l'index défini si le numéro est présent. Vous pouvez le modifier pour avoir le nombre d'occurrences de chaque numéro. Il y a une belle colonne sur les vecteurs de bits dans les perles de programmation de Bentley.
Essayez-vous de garder toute cette structure en mémoire? Les bases de données utilisent couramment un arbre B pour ce type de recherche. La structure est stockée sur le disque et ne prend qu'un petit nombre d'accès pour trouver la clé souhaitée même avec un très grand nombre de clés dans l'index.
@Jotn: Les remplissages de la ligne de cache de la CPU peuvent avoir le même effet sur les performances que la page de la base de données se lit, bien que sur microseconde plutôt que sur une échelle milliseconde.
Si vous allez utiliser un arbre d'équilibrage de l'auto-équilibrage, je vous recommande vivement de lire ce papier: web.stanford.edu/~blpp/papers/libavl.pdf