Arbres binaires vs. listes liées vs. Tables de hachage

les compromis standard entre ces structures de données s'appliquent.

• Arbres Binaires
  • complexité moyenne à mettre en œuvre (en supposant que vous ne pouvez pas les obtenir d'une bibliothèque)
  • inserts sont en O(logN)
  • des recherches sont en O(logN)
• listes liées (non triées))
  • faible complexité à mettre en œuvre
  • inserts sont en O(1)
  • des recherches sont en O(N)
• tables de hachage
  • grande complexité à mettre en œuvre
  • inserts sont en O(1) en moyenne
  • les recherches sont O (1) en moyenne

ce que tout le monde semble oublier est que pour les petits Ns, C'est à dire peu de symboles dans votre table, la liste liée peut être beaucoup plus rapide que la table de hachage, bien qu'en théorie sa complexité asymptotique est en effet plus élevé.

il y a un célèbre qoute des notes de Pike's sur la programmation en C: "Règle 3. Fantaisie algorithmes sont lents lorsque n est petit, et n est généralement faible. Les algorithmes fantaisistes ont de grandes constantes. Jusqu'à ce que vous sachiez que n va souvent être grand, ne devenez pas Fantaisie." http://www.lysator.liu.se/c/pikestyle.html

Je ne peux pas dire à partir de votre poste si vous aurez affaire à un petit N ou pas, mais toujours se rappeler que le meilleur algorithme pour les grands N ne sont pas nécessairement bons pour les petits Ns.

on dirait que ce qui suit peut être vrai:

• vos clés sont des cordes.
• Inserts sont effectuées une seule fois.
Les recherches
• sont effectuées fréquemment.
• le nombre de paires de valeurs clés est relativement petit (par exemple moins d'un K).

si oui, vous pourriez considérer une liste triée sur l'une de ces autres structures. Ce serait pire que les autres pendant inserts, comme une liste triée est O(N) sur insert, versus O(1) pour une liste liée ou une table de hachage, et O (log ₂ N) pour un arbre binaire équilibré. Mais les recherches dans une liste triée peuvent être plus rapides que n'importe laquelle de ces autres structures (je vais l'expliquer sous peu), donc vous pouvez sortir sur le dessus. En outre, si vous exécutez tous vos inserts à la fois (ou autrement ne nécessitent pas de recherche jusqu'à ce que toutes les insertions sont complètes), alors vous pouvez simplifier les insertions à O(1) et faire un tri beaucoup plus rapide à la fin. Qui plus est, une liste triée utilise moins de mémoire que n'importe laquelle de ces autres structures, mais la seule façon que cela ait de l'importance est si vous avez beaucoup de petites listes. Si vous avez une ou quelques grandes listes, puis une table de hachage est enclin à effectuer une liste triée.

Pourquoi les recherches seront plus rapides avec une liste triée? Il est clair que c'est plus rapide qu'une liste liée, avec le temps de recherche O(N) de cette dernière. Avec un arbre binaire, les recherches restent seulement O (log ₂ N) si l'arbre est parfaitement équilibré. Garder l'arbre en équilibre (rouge-noir, par exemple) ajoute à la complexité et au temps d'insertion. De plus, avec des listes liées et des arborescences binaires, chaque élément est attribué séparément. ¹ noeud , ce qui signifie que vous devrez déréférencer les pointeurs de référence et probablement sauter à des adresses mémoire potentiellement très variables, augmentant les chances d'un cache manquer.

comme pour les tables de hash, vous devrait probablement lire un couple de autres questions ici sur StackOverflow, mais les principaux points d'intérêt ici sont:

• une table de hachage peut dégénérer en O(N) dans le pire des cas.
• le coût du hachage n'est pas nul, et dans certaines implémentations il peut être important, en particulier dans le cas des chaînes.
• Comme dans les listes et arbres binaires, chaque entrée est un noeud stocker plus que la clé et la valeur, aussi séparément-alloués dans certaines implémentations, de sorte que vous utilisez plus de mémoire et augmenter les chances d'une erreur de cache.

bien sûr, si vous vous souciez vraiment de la façon dont ces structures de données fonctionneront, vous devriez les tester. Vous devriez avoir peu de difficulté à trouver de bonnes implémentations de l'un de ceux-ci pour les langues les plus courantes. Il ne devrait pas être trop difficile de jeter certains de vos données réelles à chacune de ces structures de données et voir ce qui fonctionne mieux.

1. _{il est possible pour une implémentation de pré-allouer un tableau de noeuds, ce qui aiderait avec le problème cache-miss. Je n'ai pas vu cela dans aucune implémentation réelle de listes liées ou d'arborescences binaires (pas que j'ai vu toutes, bien sûr), bien que vous puissiez certainement lancer les vôtres. Vous auriez encore une possibilité légèrement plus élevée de manquer une cache, cependant, depuis le noeud Les objets 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.

à Partir de trois choix:

sont relativement lentes à rechercher des éléments dans (O(n)). Donc, si vous avez un beaucoup d'éléments dans votre table, ou vous allez faire beaucoup de recherches, alors qu'ils ne sont pas le meilleur choix. Cependant, ils sont faciles à construire et facile à écrire aussi. Si la table est petite, et/ou vous ne faites qu'un petit scan à travers elle après il est construit, alors ce pourrait être le choix pour vous.

les tables de Hash peuvent être extrêmement rapides. Cependant, pour que cela fonctionne, vous devrez choisir un bon hachage pour votre entrée, et vous devez choisir une table assez grande pour contenir tout sans beaucoup de collisions de hachage. Ce que cela signifie est que vous devez savoir quelque chose sur la taille et la quantité de votre input. Si vous gâchez cela, vous finissez avec un ensemble très cher et complexe de listes liées. Je dirais ça à moins que tu ne saches à l'avance le temps à peu près combien la table va être, ne pas utiliser une table de hachage. Ceci n'est pas d'accord avec votre réponse" acceptée". Désolé.

qui laisse des arbres. Vous avez une option ici cependant: é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 est que l'entrée de la table de symboles tend à être suffisamment aléatoire que vous perdez seulement environ un niveau d'arbre ou deux en ne équilibrant pas l'arbre. Étant donné que les arbres équilibrés sont plus lents à insérer des éléments Dans et sont plus difficiles à mettre en œuvre, Je ne m'embêterais pas avec eux. Cependant, si vous avez déjà accès à de belles bibliothèques de composants débogués (par exemple: STL de C++), alors vous pouvez aussi bien aller de l'avant et utiliser l'arbre équilibré.

deux ou trois choses à surveiller.

• les arbres binaires ont seulement une recherche O(log n) et insèrent la complexité si l'arbre est équilibré . Si vos symboles sont insérés de façon assez aléatoire, cela ne devrait pas poser de problème. S'ils sont insérés dans l'ordre, vous construirez une liste liée. (Pour votre application spécifique, ils ne devraient pas être dans n'importe quel ordre, donc vous devriez être d'accord.) Si il y a une chance que l' les symboles seront trop ordonnés, un arbre Rouge-Noir est une meilleure option.

• les tables de hachage donnent O(1) Moyenne insertion et la complexité de la recherche, mais il ya une mise en garde ici, aussi. Si votre fonction de hachage est mauvaise (et je veux dire vraiment Mauvaise) vous pourriez finir par construire une liste liée ici aussi bien. N'importe quelle fonction de hachage de chaîne raisonnable devrait faire, cependant, de sorte que cet avertissement est vraiment seulement pour s'assurer que vous êtes au courant qu'il pourrait arriver. Vous devriez être en mesure de tester que votre fonction de hachage n'a pas beaucoup de collisions au-dessus de votre gamme attendue d'entrées, et vous serez très bien. Un autre inconvénient mineur est si vous utilisez une table de hachage de taille fixe. La plupart des mises en place de tables de hachage croissent lorsqu'elles atteignent une certaine taille (facteur de charge pour être plus précis, voir ici pour plus de détails). Ceci est pour éviter le problème que vous obtenez lorsque vous insérez un million de symboles dans dix seaux. Qui mène juste à dix liés listes avec une taille moyenne de 100 000.

• Je n'utiliserais une liste liée que si j'avais une table de symboles vraiment courte. C'est plus facile à mettre en œuvre, mais la meilleure performance pour une liste liée est la pire performance pour vos deux autres options.

D'autres commentaires ont mis l'accent sur l'ajout/la récupération d'éléments, mais cette discussion n'est pas complète sans tenir compte de ce qu'il faut pour itérer sur l'ensemble de la collection. La réponse courte ici est que les tables de hachage nécessitent moins de mémoire pour itérer plus, mais les arbres exigent moins de temps.

pour une table de hachage, la mémoire supérieure de l'itération sur les paires (clé, valeur) ne dépend pas de la capacité de la table ou le nombre d'éléments stockés dans la table; en fait, l'itération ne devrait nécessiter qu'une ou deux variables d'indice.

Pour les arbres, la quantité de mémoire requise dépend toujours de la taille de l'arbre. Vous pouvez soit maintenir une file d'attente de noeuds non visités pendant l'itération, soit ajouter des pointeurs supplémentaires à l'arbre pour faciliter l'itération (ce qui fait que l'arbre, pour les fins de l'itération, agit comme une liste liée), mais de toute façon, vous devez allouer de la mémoire supplémentaire pour l'itération.

mais la situation est inversée quand il vient le moment. Pour une table de hachage, le temps qu'il faut pour effectuer une itération dépend de la capacité de la table, pas le nombre d'éléments stockés. Ainsi, une table chargée à 10% de sa capacité prendra environ 10 fois plus de temps à itérer qu'une liste liée avec les mêmes éléments!

Cela dépend de plusieurs choses, bien sûr. Je dirais qu'une liste liée est tout de suite dehors, puisqu'il a peu de propriétés appropriées pour travailler comme une table de symbole. Un arbre binaire 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 pour ce but.

cette question passe par les différents conteneurs en C#, mais ils sont similaires dans n'importe quelle langue que vous utilisez.

à moins que vous ne vous attendiez à ce que votre table de symboles soit petite, je devrais éviter les listes liées. Une liste de 1000 items prendra en moyenne 500 itérations pour trouver n'importe quel item à l'intérieur d'elle.

un arbre binaire peut être beaucoup plus rapide, tant qu'il est équilibré. Si vous persistez dans le contenu, la forme sérialisée sera probablement triée, et quand elle sera rechargée, l'arbre résultant sera totalement déséquilibré en conséquence, et il se comportera de la même façon que la liste liée - parce que c'est en gros ce qu'il est devenu. Des algorithmes d'arbres équilibrés résolvent ce problème, mais rendent l'ensemble plus complexe.

une hashmap (à condition de choisir un algorithme de hachage approprié) semble être la meilleure solution. Vous n'avez pas mentionné votre environnement, mais à peu près toutes les langues modernes ont un Hashmap intégré.