Conversion d'identificateurs d'entier en pointeurs

Question

J'ai des valeurs d'ID du type unsigned int. J'ai besoin de mapper un Id à un pointeur en temps constant.

---

Key Distribution:

ID aura une valeur dans la plage de 0 à UINT_MAX. La plupart des clés seront regroupées en un seul groupe, mais il y aura des valeurs aberrantes.

---

Mise en œuvre:

• je pensais à utiliser le C++ choses ext hash_map, mais je l'ai entendu leur performance ne soit pas trop grand lorsque les touches ont une vaste gamme de potentiel.

• J'ai aussi pensé à utiliser une forme de recherche chaînée (équivalente à une subdivision récursive de la gamme en mandrins C). S'il n'y a pas de clés dans une plage, cette plage pointe vers NULL.

  N = Key Range

  Niveau 0 (C = divisé en 16, de sorte 16 pièces) = [0, N/16), [N/16, 2 * (N/16)), .. .

  Niveau 1 (divisé en C = 16, donc 16 * 16 pièces) = ...

---

quelqu'un d'autre a des idées sur la façon dont cette cartographie peut être plus efficacement mis en œuvre?

Mise à jour:

En constante, je voulais juste dire chaque recherche clé est pas significativement influencée par le nombre de valeurs dans l'élément. Je ne voulais pas dire que ça devait être une seule opération.

Answer 1

Utilisez une carte de hachage (unordered_map). Cela donne ~ O (1) temps de recherche. Vous avez "entendu" que c'était mauvais, mais l'avez-vous essayé, testé, et déterminé que c'était un problème? Sinon, utilisez une carte de hachage. Une fois que votre code est presque terminé, mettez-le en profil et déterminez si les temps de recherche sont la principale cause de lenteur dans votre programme. Les chances sont, ce ne sera pas.

Answer 2

Vous n'obtiendrez pas de temps constant.

Je serais probablement utiliser un B+Tree

Answer 3

Si vos valeurs entières 32 bits de largeur, vous pouvez utiliser une plate-forme 64 bits, allouez 32 giga-octets de mémoire (8 octets par 4 milliards de pointeurs), et l'utilisation un tableau plat. Ce sera aussi proche que vous allez obtenir à temps de recherche constante.

Answer 4

Réservez 4 Go de RAM pour cela, et lancez simplement votre uint sur le pointeur. C'est définitivement le temps constant.

Answer 5

Si vous voulez une solution arborescente et vos identifiants sont dans la plage {0 ..n-1} alors vous pouvez utiliser une structure de données très cool appelée van Emde Boas tree. Cela donnera toutes les opérations dans O (log log n) et utilisera l'espace O (n).

Answer 6

Comme GMan suggère qu'une carte non ordonnée est probablement une bonne solution. Si vous êtes préoccupé par un grand nombre de collisions dans cette carte de hachage, utilisez une fonction de hachage qui supprimera le clustering de vos données. Par exemple, vous pouvez échanger les octets autour. Un bon point à noter est que vous passerez probablement plus de temps à déboguer et à prouver une structure de données personnalisée que celle qui a déjà un bon pedigree.

Answer 7

Combien d'éléments doivent figurer dans une telle carte et à quelle fréquence est-elle modifiée?

Si toutes les valeurs correspondent à la mémoire cache du processeur, un std::vector<std::pair<unsigned int,T*>> avec des valeurs pré-réglées et une recherche binaire peut être le plus rapide malgré l'accès O (N).