Arbres binarys vs listes liées vs tables de hachage

Votre cas d’utilisation va probablement être “insérer les données une fois (par exemple, le démarrage de l’application) et ensuite effectuer un grand nombre de lectures, mais peu, voire aucune insertion supplémentaire”.

Par conséquent, vous devez utiliser un algorithme rapide pour rechercher les informations dont vous avez besoin.

Je pense donc que HashTable était l’algorithme le plus approprié à utiliser, car il génère simplement un hachage de votre object clé et l’utilise pour accéder aux données cibles – c’est O (1). Les autres sont O (N) (Listes liées de taille N – vous devez parcourir la liste une par une, une moyenne de N / 2 fois) et O (log N) (Arbre binary – vous divisez par deux l’espace de recherche avec chaque itération – seulement si l’arbre est équilibré, donc cela dépend de votre implémentation, une arborescence déséquilibrée peut avoir des performances nettement moins bonnes).

Assurez-vous qu’il y a suffisamment d’espaces (compartiments) dans le HashTable pour vos données (commentaire de Re, Soraz sur ce post). La plupart des implémentations de framework (Java, .NET, etc.) seront d’une qualité que vous n’aurez pas à vous soucier des implémentations.

Avez-vous suivi un cours sur les structures de données et les algorithmes à l’université?

Les compromis standard entre ces structures de données s’appliquent.

• Arbres binarys
  • complexité moyenne à mettre en œuvre (en supposant que vous ne pouvez pas les obtenir d’une bibliothèque)
  • les inserts sont O (logN)
  • les recherches sont O (logN)
• Listes liées (non sortingées)
  • faible complexité à mettre en œuvre
  • les inserts sont O (1)
  • les recherches sont O (N)
• Tables de hachage
  • haute complexité à mettre en œuvre
  • les insertions sont O (1) en moyenne
  • les recherches sont en moyenne O (1)

Ce que tout le monde semble oublier, c’est que pour les petits N, IE peu de symboles dans la table, la liste chaînée peut être beaucoup plus rapide que la table de hachage, bien qu’en théorie sa complexité asymptotique soit plus élevée.

Il existe un qoute célèbre des Notes de Pike sur la programmation en C: “Règle 3. Les algorithmes de fantaisie sont lents quand n est petit et n est généralement petit. Les algorithmes de fantaisie ont de grandes constantes. Jusqu’à ce que vous sachiez ne pas avoir envie. ” http://www.lysator.liu.se/c/pikestyle.html

Je ne peux pas dire à partir de votre post si vous avez affaire à un petit N ou non, mais souvenez-vous toujours que le meilleur algorithme pour les grands N n’est pas nécessairement bon pour les petits N.

Il semble que ce qui suit peut être vrai:

• Vos clés sont des chaînes.
• Les insertions sont faites une fois.
• Les recherches sont effectuées fréquemment.
• Le nombre de paires clé-valeur est relativement faible (disons moins d’un K ou presque).

Si c’est le cas, vous pourriez envisager une liste sortingée sur l’une de ces autres structures. Cela fonctionnerait moins bien que les autres pendant les insertions, car une liste sortingée est O (N) lors de l’insertion, contre O (1) pour une liste liée ou une table de hachage, et O (log ₂ N) pour un arbre binary équilibré. Mais les recherches dans une liste sortingée peuvent être plus rapides que n’importe laquelle de ces autres structures (je vous expliquerai cela sous peu), de sorte que vous pouvez être en tête. De plus, si vous effectuez toutes vos insertions à la fois (ou si vous n’avez pas besoin de recherches avant que toutes les insertions ne soient terminées), vous pouvez simplifier les insertions dans O (1) et effectuer un sorting beaucoup plus rapide à la fin. De plus, une liste sortingée utilise moins de mémoire que n’importe laquelle de ces autres structures, mais la seule façon de procéder est probablement d’avoir beaucoup de petites listes. Si vous avez une ou plusieurs grandes listes, une table de hachage est susceptible de surpasser une liste sortingée.

Pourquoi les recherches peuvent-elles être plus rapides avec une liste sortingée? Eh bien, il est clair que c’est plus rapide qu’une liste chaînée, avec le temps de recherche O (N) de ce dernier. Avec un arbre binary, les recherches ne restnt que O (log ₂ N) si l’arbre rest parfaitement équilibré. Garder l’arbre équilibré (rouge-noir, par exemple) ajoute à la complexité et au temps d’insertion. De plus, à la fois avec les listes liées et les arbres binarys, chaque élément est un nœud ¹ distinct, ce qui signifie que vous devrez déréférencer les pointeurs et passer à des adresses de mémoire potentiellement très variées, augmentant ainsi les risques d’échec du cache.

En ce qui concerne les tables de hachage, vous devriez probablement lire quelques autres questions sur StackOverflow, mais les principaux points d’intérêt sont les suivants:

• Une table de hachage peut dégénérer en O (N) dans le pire des cas.
• Le coût du hachage est différent de zéro et, dans certaines implémentations, il peut être important, en particulier dans le cas des chaînes de caractères.
• Comme dans les listes liées et les arborescences binarys, chaque entrée est un nœud stockant plus que des clés et des valeurs, également allouées séparément dans certaines implémentations, de sorte que vous utilisez plus de mémoire et augmentez les risques d’échec du cache.

Bien sûr, si vous vous souciez vraiment du fonctionnement de ces structures de données, vous devriez les tester. Vous devriez avoir peu de problèmes pour trouver de bonnes implémentations de l’un de ces langages pour la plupart des langages courants. Il ne devrait pas être trop difficile de lancer certaines de vos données réelles sur chacune de ces structures de données et de voir celles qui fonctionnent le mieux.

1. _{Il est possible pour une implémentation de pré-allouer un tableau de nœuds, ce qui aiderait à résoudre le problème de cache-miss. Je n’ai pas vu cela dans une implémentation réelle de listes liées ou d’arbres binarys (pas que j’ai vu tout le monde, bien sûr), bien que vous puissiez certainement faire votre propre. Vous auriez quand même une possibilité légèrement plus élevée de manquer de cache, car les objects de noeud seraient nécessairement plus grands que les paires clé / valeur.}

J’aime la réponse de Bill, mais elle ne synthétise pas vraiment les choses.

Parmi les trois choix:

Les listes liées sont relativement lentes pour rechercher des éléments de (O (n)). Donc, si vous avez beaucoup d’éléments dans votre table, ou vous allez faire beaucoup de recherches, alors ce n’est pas le meilleur choix. Cependant, ils sont faciles à construire et faciles à écrire. Si la table est petite et / ou si vous ne faites qu’une petite parsing après sa création, cela peut être le choix pour vous.

Les tables de hachage peuvent être extrêmement rapides. Cependant, pour que cela fonctionne, vous devez choisir un bon hash pour votre saisie, et vous devez choisir une table assez grande pour contenir tout sans beaucoup de collisions de hachage. Cela signifie que vous devez savoir quelque chose sur la taille et la quantité de vos données. Si vous vous trompez, vous vous retrouvez avec un ensemble très coûteux et complexe de listes liées. Je dirais que, à moins que vous ne sachiez à l’avance quelle sera la taille de la table, n’utilisez pas de table de hachage. Ceci n’est pas d’accord avec votre réponse “acceptée”. Pardon.

Cela laisse des arbres. Vous avez cependant une option ici: équilibrer ou ne pas équilibrer. Ce que j’ai trouvé en étudiant ce problème sur le code C et Fortran que nous avons ici, c’est que l’entrée de la table des symboles tend à être suffisamment aléatoire pour ne perdre qu’un niveau d’arbre ou deux en n’équilibrant pas l’arbre. Étant donné que les arbres équilibrés sont plus lents à insérer dans les éléments et sont plus difficiles à mettre en œuvre, je ne les dérangerais pas. Cependant, si vous avez déjà access à de belles bibliothèques de composants de débogage (ex: STL de C ++), alors vous pouvez aussi aller de l’avant et utiliser l’arbre équilibré.

Un couple de choses à surveiller.

• Les arbres binarys n’ont qu’une recherche O (log n) et une complexité d’insertion si l’arbre est équilibré . Si vos symboles sont insérés de manière assez aléatoire, cela ne devrait pas poser de problème. Si elles sont insérées dans l’ordre, vous allez créer une liste liée. (Pour votre application spécifique, ils ne devraient pas être dans n’importe quel ordre, alors vous devriez être d’accord.) S’il y a une chance que les symboles soient trop ordonnés, un arbre rouge-noir est une meilleure option.

• Les tables de hachage donnent à O (1) une complexité d’insertion et de recherche moyenne, mais il y a une mise en garde ici aussi. Si votre fonction de hachage est mauvaise (et je veux dire vraiment mauvaise), vous pourriez également créer une liste de liens. Toute fonction de hachage de chaîne raisonnable devrait faire, cependant, cet avertissement est vraiment uniquement pour vous assurer que vous êtes conscient que cela pourrait se produire. Vous devriez être en mesure de tester que votre fonction de hachage n’a pas beaucoup de collisions sur votre plage d’entrées attendue, et tout ira bien. Un autre inconvénient mineur est si vous utilisez une table de hachage de taille fixe. La plupart des implémentations de tables de hachage augmentent lorsqu’elles atteignent une certaine taille (le facteur de charge est plus précis, voir ici pour plus de détails). Ceci pour éviter le problème que vous rencontrez lorsque vous insérez un million de symboles dans dix compartiments. Cela ne mène qu’à dix listes liées d’une taille moyenne de 100 000.

• Je n’utiliserais qu’une liste chaînée si j’avais une table de symboles très courte. Il est plus facile à implémenter, mais la meilleure performance de cas pour une liste chaînée est la pire des performances pour vos deux autres options.

D’autres commentaires ont porté sur l’ajout / récupération d’éléments, mais cette discussion n’est pas complète sans considérer ce qu’il faut faire pour parcourir toute la collection. La réponse courte ici est que les tables de hachage nécessitent moins de mémoire pour itérer, mais les arbres nécessitent moins de temps.

Pour une table de hachage, le surcoût de l’itération sur les paires (clé, valeur) ne dépend pas de la capacité de la table ou du nombre d’éléments stockés dans la table; en fait, l’itération ne devrait nécessiter qu’une seule variable d’index ou deux.

Pour les arbres, la quantité de mémoire requirejse dépend toujours de la taille de l’arborescence. Vous pouvez soit conserver une queue de nœuds non visités lors de l’itération, soit append des pointeurs supplémentaires à l’arborescence pour faciliter l’itération (faire de l’arborescence, à des fins d’itération, une liste liée), mais vous devez .

Mais la situation est inversée en ce qui concerne le calendrier. Pour une table de hachage, le temps nécessaire à l’itération dépend de la capacité de la table et non du nombre d’éléments stockés. Ainsi, une table chargée à 10% de capacité prendra environ 10 fois plus de temps pour parcourir une liste chaînée contenant les mêmes éléments!

Cela dépend de plusieurs choses, bien sûr. Je dirais qu’une liste de liens est exacte, car elle a peu de propriétés appropriées pour fonctionner comme une table de symboles. Un arbre binary peut fonctionner si vous en avez déjà un et que vous n’avez pas à passer du temps à l’écrire et le déboguer. Mon choix serait une table de hachage, je pense que c’est plus ou moins la valeur par défaut à cette fin.

Cette question passe par les différents conteneurs en C #, mais ils sont similaires dans toutes les langues que vous utilisez.

Sauf si vous vous attendez à ce que votre table de symboles soit petite, je devrais éviter les listes liées. Une liste de 1 000 éléments nécessitera en moyenne 500 itérations pour trouver un élément.

Un arbre binary peut être beaucoup plus rapide tant qu’il est équilibré. Si vous conservez le contenu, le formulaire sérialisé sera probablement sortingé, et lorsqu’il sera rechargé, l’arborescence résultante sera totalement déséquilibrée et se comportera comme la liste des liens, car essentiellement ce qu’il est devenu. Les algorithmes d’arborescence équilibrée résolvent ce problème, mais rendent le shebang plus complexe.

Un hashmap (à condition que vous choisissiez un algorithme de hachage approprié) ressemble à la meilleure solution. Vous n’avez pas mentionné votre environnement, mais à peu près tous les langages modernes ont un Hashmap intégré.