Meilleur Algorithme pour paire clé/valeur où la clé est un int64 dans Delphi, pré Delphi 2009?

Question

J'ai besoin d'un algorithme pour stocker une paire clé/valeur, où la clé est un Int64. J'utilise actuellement une IntList triée (identique à une TStringList, mais stocke des int64). Cela me donne O (log n) pour les opérations de recherche, d'insertion et de suppression. Comme je n'ai jamais besoin d'articles triés, c'est un peu inefficace. J'ai besoin d'une sorte de hashtable pour les opérations O (1). Le problème est que la plupart des implémentations que je peux trouver supposent que la clé est une chaîne. Maintenant, je pourrais évidemment convertir la clé Int64 en une chaîne, mais cela semble inutile. Des idées?

Je ne connais pas le nombre d'éléments avant qu'ils ne soient entrés dans la structure de données. Je dois également ajouter que j'ai implémenté le même composant dans .net, en utilisant Dictionary, et qu'il ajoute les éléments qui sont tellement plus rapides dans la version .net. Une fois la structure de données configurée, les parcours et les récupérations ne sont pas si mauvais en comparaison, mais c'est l'insertion qui me tue.

Answer 1

Delphi 2009 et versions ultérieures ont ajouté des génériques. Ainsi, à partir de Delphi 2009, vous pouvez implémenter votre paire clé/valeur de la même manière que vous le faites dans .NET en utilisant un TDICTIONARY.

et TDICTIONARY dans Delphi utilise une table de table de hachage et a des opérations O (1).

Answer 2

Vous pouvez construire une table de hachage, où la valeur de hachage est un simple module de l'Int64 que vous ajoutez au hachage.

Toute bonne implémentation de table de hachage aura la génération de l'index de hachage (en hachant la clé) séparée du reste de la logique.

Certaines implémentations sont résumées ici: Hashtable implementation for Delphi 5

Answer 3

Quelques réflexions, pas une solution complète soufflée.

À moins qu'il n'y ait une preuve définitive que la recherche elle-même est le goulot d'étranglement (n'utilisez pas votre «sentiment» pour détecter les goulots d'étranglement, utilisez un profileur de code) Je resterais avec le IntList ... recherche/insertion/suppression ne représente pas au moins 20% de la durée totale du processeur, ne vous embêtez même pas.

Si vous voulez encore une table de hachage, puis ...

Ne pas convertir en une chaîne. La conversion allouerait une nouvelle chaîne à partir du tas, ce qui est beaucoup plus coûteux que de faire la recherche elle-même. Utilisez le module int64 modulo un nombre premier judicieusement choisi comme clé de hachage.

Les tables de hachage ne vous donneront O (1) que si elles sont assez grandes. Sinon, vous obtiendrez une grande quantité d'enregistrements partageant la même clé de hachage. Faites-en trop court, vous perdrez votre temps à chercher (linéairement!) À travers la liste chaînée. Faites-en trop, et vous perdez de la mémoire. Gardez à l'esprit que les tables de hachage requièrent une forme de liste liée pour conserver tous les enregistrements partageant la même clé. Cette liste chaînée doit être implémentée soit en ajoutant un pointeur "suivant" dans les objets utiles (qui casse l'encapsulation - l'objet n'a pas besoin de savoir qu'elle est stockée dans une table de hachage) soit en allouant un petit objet auxiliaire. Cette allocation est susceptible d'être beaucoup plus coûteuse que l'O (log) de la liste triée.

Answer 4

Vous pouvez calculer une valeur de hachage directement à partir de la valeur int64, mais pour cela vous devez trouver une fonction de hachage qui distribue uniformément les différentes valeurs int64, de sorte que vous obteniez peu ou pas de collisions. Cela dépend bien sûr des valeurs de ces clés. Si vous ne connaissez pas le nombre d'éléments, vous ne savez probablement pas comment ces valeurs int64 sont distribuées, il sera donc difficile de trouver une bonne fonction de hachage. En supposant que vos clés ne sont pas des multiples de quelque chose (comme des adresses, qui seront des multiples de 4, 8, 16 et ainsi de suite) vous pourriez accélérer un peu en utilisant une liste de plusieurs de ces objets IntList, et calculer d'abord un index dans ce tableau de listes.L'utilisation de l'opérateur mod et d'un nombre premier serait un moyen facile de calculer l'index de la liste. Comme toujours, il s'agit d'un compromis entre la vitesse et la consommation de mémoire.

Vous pouvez également rechercher une bonne implémentation de baies clairsemées sur google. IIRC la bibliothèque EZDSL par Julian Bucknall a un.