Les arbres binaires par rapport aux listes chaînées vs tables de hachage

StackOverflow https://stackoverflow.com/questions/371136

Question

Je construis une table de symboles pour un projet sur lequel je travaille. Je me demandais ce que les peuples opinions sont sur les avantages et les inconvénients des différentes méthodes disponibles pour le stockage et la création d'une table de symboles.

Je l'ai fait un peu juste de la recherche et le plus souvent recommandé sont des arbres binaires ou les listes chaînées ou des tables de hachage. Quels sont les avantages et les inconvénients ou de tout ce qui précède? (Travaillant en C ++)

Était-ce utile?

La solution

Votre cas d'utilisation va probablement être « insérer les données une fois (par exemple, le démarrage de l'application), puis effectuez beaucoup de lectures, mais peu ou pas des insertions supplémentaires ».

Par conséquent, vous devez utiliser un algorithme qui est rapide pour rechercher des informations que vous avez besoin.

Je pense donc Hashtable est l'algorithme le plus approprié à utiliser, car il génère simplement un hachage de votre objet clé et à l'aide que pour accéder aux données cible - est O (1). Les autres sont O (N) (listes chaînées de taille N - vous devez parcourir la liste un à la fois, en moyenne N / 2 fois) et O (log N) (Binary Tree - vous réduire de moitié l'espace de recherche avec chaque itération -. que si l'arbre est équilibré, donc cela dépend de votre mise en œuvre, un arbre déséquilibré peut avoir des performances nettement moins bonne)

Assurez-vous qu'il ya assez de places (seaux) dans la table de hachage pour vos données (R.E., commentaire de Soraz sur ce post). La plupart des implémentations cadres (Java, .NET, etc.) seront d'une qualité que vous aurez pas besoin de vous soucier des mises en œuvre.

Avez-vous fait un cours sur les structures et les algorithmes données à l'université?

Autres conseils

Les compromis standard entre ces structures de données applicables.

  • Les arbres binaires
    • complexité moyenne à mettre en œuvre (en supposant que vous ne pouvez pas les obtenir à partir d'une bibliothèque)
    • inserts sont O (logN)
    • recherches sont O (logN)
  • Les listes chaînées (non triés)
    • faible complexité de la mise en œuvre
    • inserts sont O (1)
    • recherches sont O (N)
  • tables de hachage
    • haute complexité à mettre en œuvre
    • inserts sont O (1) en moyenne
    • recherches sont O (1) en moyenne

Qu'est-ce que tout le monde semble oublier que pour les petits Ns, IE quelques symboles dans votre table, la liste chaîné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 sur la programmation en C:. « Règle 3. Les algorithmes complexes sont lents lorsque n est faible, et n est généralement faible des algorithmes de fantaisie ont de grandes constantes Jusqu'à ce que vous savez que n va souvent. être grand, ne pas fantaisie « . http://www.lysator.liu.se/c/pikestyle.html

Je ne peux pas dire de votre poste si vous aurez affaire à un petit N ou non, mais rappelez-vous toujours que le meilleur algorithme de grande N ne sont pas nécessairement de bon pour les petits Ns.

On dirait que ce qui suit peut être vrai:

  • Vos clés sont des chaînes.
  • Les inserts sont fait une fois.
  • Lookups se font souvent.
  • Le nombre de paires clé-valeur est relativement faible (par exemple, moins d'un K ou plus).

Si oui, vous pourriez envisager une liste triée sur l'un de ces structures. Cela de moins bons résultats que les autres lors des insertions, comme une liste triée est O (N) sur insert, par rapport à O (1) pour une liste chaînée ou table de hachage, et O (log 2 N) pour un arbre binaire équilibré. Mais dans une liste lookups triée peut être plus rapide que l'une de ces structures autres (je vais vous expliquer ce peu), de sorte que vous pouvez sortir par le haut. En outre, si vous effectuez vos opérations d'encartage à la fois (ou autrement ne nécessitent que toutes les insertions lookups sont terminées), vous pouvez simplifier les insertions O (1) et faire une sorte beaucoup plus rapide à la fin. De plus, une liste triée utilise moins de mémoire que l'une de ces autres structures, mais la seule façon il est probable que la matière est que si vous avez beaucoup de petites listes. Si vous avez un ou quelques grandes listes, puis une table de hachage est susceptible de surclasser une liste triée.

Pourquoi peut-être plus rapide des recherches avec une liste triée? Eh bien, il est clair qu'il est plus rapide qu'une liste chaînée, avec O (N) temps de recherche de ce dernier. Avec un arbre binaire, restent seulement O lookups (log 2 N) si l'arbre reste parfaitement équilibré. Garder l'arbre équilibré (rouge-noir, par exemple) ajoute à la complexité et le temps d'insertion. De plus, avec les deux listes chaînées et les arbres binaires, chaque élément est un séparément alloué 1 noeud , ce qui signifie que vous aurez à des pointeurs de déréférencer et saut susceptibles de potentiellement très variables adresses de mémoire, ce qui augmente les chances d'un défaut de cache.

Comme pour les tables de hachage, vous devriez probablement un couple de questions ici sur StackOverflow, mais les principaux points d'intérêt ici sont:

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

Bien sûr, si vous tenez vraiment à voir comment ces structures de données se produiront, vous devriez les tester. Vous devriez avoir peu de problème à trouver de bonnes implémentations de l'une de ces langues pour la plupart des communes. Il ne devrait pas être trop difficile de jeter certaines 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 mise en œuvre de pré-allouer un tableau de noeuds, ce qui aiderait le problème cache-miss. Je ne l'ai pas vu cela dans une mise en œuvre réelle des listes chaînées ou des arbres binaires (pas que je l'ai vu tout le monde, bien sûr), bien que vous pourriez certainement rouler votre propre. Vous auriez toujours une possibilité d'un défaut de cache légèrement plus élevé, cependant, puisque le noeud objets serait nécessairement plus grande que les paires clé / valeur.

J'aime la réponse de Bill, mais il ne synthétisent pas vraiment les choses.

A partir des trois choix:

listes chaînées sont relativement lents pour rechercher des éléments de (O (n)). Donc, si vous avez un beaucoup d'éléments dans votre table, ou vous allez faire beaucoup de recherches, ils ne sont pas le meilleur choix. Cependant, ils sont faciles à construire et facile à écrire aussi. Si la table est petite, et / ou que vous ne faites jamais un petit balayage à travers elle après sa construction, alors cela pourrait être le choix pour vous.

tables de hachage peuvent être extrêmement rapide. Cependant, pour qu'il vous faut travailler 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 entrée. Si vous vous trompez tout ça, vous vous retrouvez avec un ensemble très coûteux et complexe de listes chaînées. Je dirais que si vous savez à l'avance à peu près la taille de la table va être, ne pas utiliser une table de hachage. Ce désaccord avec votre réponse « acceptée ». Désolé.

Il reste des arbres. Vous avez une option ici si: Pour équilibrer ou non à l'équilibre. 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 des symboles a tendance à être assez aléatoire que vous perdez seulement un niveau d'arbre ou deux en n'équilibrant 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 viendrais pas avec eux. Toutefois, si vous avez déjà accès à des bibliothèques de composants agréables débogué (par exemple: C ++ 's STL)., Alors vous pourriez aussi bien aller de l'avant et d'utiliser l'arbre équilibré

Un couple de choses à surveiller.

D'autres commentaires se sont concentrés sur l'ajout / la récupération des éléments, mais cette discussion n'est pas complète sans tenir compte de ce qu'il faut pour parcourir la collection. La réponse courte est que les tables de hachage nécessitent moins de mémoire à itérer, mais les arbres nécessitent moins de temps.

Pour une table de hachage, la surcharge de la mémoire de l'itération sur la (clé, valeur) paires ne dépend pas de la capacité de la table ou le nombre d'éléments mémorisés dans la table; en fait, itérer devrait exiger une seule variable d'index ou deux.

Pour les arbres, la quantité de mémoire requise dépend toujours de la taille de l'arbre. Vous pouvez maintenir une file d'attente de nœuds inexplorées en itérer ou ajouter des pointeurs supplémentaires à l'arbre pour l'itération plus facile (rendant l'arbre, à des fins d'itération, agir comme une liste chaîné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 en ce qui concerne le calendrier. Pour une table de hachage, le temps qu'il faut pour itérer dépend de la capacité de la table, et non le nombre d'éléments stockés. Ainsi, une table chargée à 10% de la capacité prendra environ 10 fois plus à parcourir qu'une liste chaînée avec les mêmes éléments!

Cela dépend de plusieurs choses, bien sûr. Je dirais qu'une liste liée est située juste, car il a peu de propriétés appropriées pour travailler comme une table de symboles. Un arbre binaire pourrait fonctionner, si vous avez déjà un et ne pas passer du temps à écrire et déboguer. Mon choix serait une table de hachage, je pense que c'est plus ou moins la valeur par défaut à cet effet.

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

Sauf si vous attendez votre table de symbole à petit, j'éviter des listes chaînées. Une liste de 1000 articles sera en moyenne prendre 500 itérations pour trouver un élément à l'intérieur.

Un arbre binaire peut être beaucoup plus rapide, tant qu'il est équilibré. Si vous êtes persistant le contenu, la forme sérialisé sera triée probable, et quand il est à nouveau chargé, l'arbre résultant sera entièrement non équilibré en conséquence, et il va se comporter de la même que la liste chaînée - parce que ce essentiellement ce qu'il est devenu. algorithmes d'arbres équilibrés résoudre cette question, mais font plus complexe tout le tralala.

A hashmap (tant que vous choisissez un algorithme de hachage approprié) ressemble à la meilleure solution. Vous ne l'avez pas parlé de votre environnement, mais à peu près toutes les langues modernes ont un hashmap construit.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top