Arbres binaires vs. Listes chaînées vs. Tables de hachage

Question

Je suis en train de construire une table des symboles pour un projet sur lequel je travaille. Je me demandais quels sont les avis des gens sur les avantages et les inconvénients des différentes méthodes disponibles pour stocker et créer une table des symboles.

J'ai fait pas mal de recherches et les méthodes les plus souvent recommandées sont les arbres binaires, les listes chaînées ou les tables de hashage. Quels sont les avantages et/ou inconvénients de chacune de ces méthodes? (travaillant en c++)

Answer 1

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 à partir d'une bibliothèque)
  • les inserts sont O(logN)
  • les recherches sont O(logN)
• Listes chaînées (non trié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 inserts sont O(1) en moyenne
  • les recherches sont O(1) en moyenne

Answer 2

Votre cas d'utilisation est probablement de "insérer les données une fois (par exemple, au démarrage de l'application) et ensuite effectuer beaucoup 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 la HashTable était l'algorithme le plus adapté à utiliser, car il génère simplement un hachage de votre objet clé et l'utilise pour accéder aux données cibles - c'est O(1). Les autres sont O(N) (Listes chaînées de taille N - vous devez parcourir la liste un à un, en moyenne N/2 fois) et O(log N) (Arbre binaire - vous divisez par deux l'espace de recherche à chaque itération - uniquement si l'arbre est équilibré, donc cela dépend de votre implémentation, un arbre déséquilibré peut avoir des performances significativement pires).

Assurez-vous simplement qu'il y a suffisamment d'espaces (buckets) dans la HashTable pour vos données (voir le commentaire de Soraz sur ce post). La plupart des implémentations de frameworks (Java, .NET, etc.) seront de qualité, vous n'aurez donc pas à vous soucier des implémentations.

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

Answer 3

Ce que tout le monde semble oublier, c'est que pour de petits N, c'est-à-dire peu de symboles dans votre tableau, la liste chaînée peut être beaucoup plus rapide que la table de hachage, bien que en théorie sa complexité asymptotique soit en effet plus élevée.

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

Je ne peux pas dire d'après votre message si vous allez traiter avec un petit N ou non, mais rappelez-vous toujours que le meilleur algorithme pour de grands N n'est pas nécessairement bon pour les petits N.

Answer 4

Il semblerait que ce qui suit puisse être vrai :

• Vos clés sont des chaînes de caractères.
• Les insertions se font une seule fois.
• Les recherches sont fréquentes.
• Le nombre de paires clé-valeur est relativement faible (disons, moins d'un K ou ainsi).

Dans ce cas, vous pourriez envisager une liste triée par rapport à ces autres structures. Cela sera moins performant que les autres lors des insertions, car une liste triée est en O(N) lors de l'insertion, par rapport à O(1) pour une liste chaîné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 dans ces autres structures (je vais l'expliquer bientôt), donc vous pourriez vous en sortir. De plus, si vous effectuez toutes vos insertions en une fois (ou si vous n'avez pas besoin de recherches avant que toutes les insertions soient terminées), alors vous pouvez simplifier les insertions en O(1) et faire un tri beaucoup plus rapide à la fin. De plus, une liste triée utilise moins de mémoire que ces autres structures, mais cela n'aura probablement d'importance que si vous avez de nombreuses petites listes. Si vous avez une ou quelques grandes listes, alors une table de hachage est susceptible de mieux fonctionner qu'une liste triée.

Pourquoi les recherches pourraient-elles être plus rapides avec une liste triée? Eh bien, il est clair que c'est plus rapide qu'une liste chaînée, avec le temps de recherche en O(N) de cette dernière. Avec un arbre binaire, les recherches ne restent en O(log₂N) que si l'arbre reste parfaitement équilibré. Garder l'arbre équilibré (rouge-noir, par exemple) ajoute à la complexité et au temps d'insertion. De plus, avec les listes chaînées et les arbres binaires, chaque élément est un1 nœud séparément alloué, ce qui signifie que vous devrez déréférencer des pointeurs et probablement accéder à des adresses mémoire potentiellement très éloignées, augmentant les chances de manquer le cache.

En ce qui concerne les tables de hachage, vous devriez probablement lire quelques autres questions ici 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 cas.
• Le coût du hachage n'est pas nul, et dans certaines implémentations, il peut être significatif, en particulier dans le cas des chaînes de caractères.
• Comme dans les listes chaînées et les arbres binaires, chaque entrée est un nœud stockant plus que juste la clé et la valeur, également séparément allouée dans certaines implémentations, donc vous utilisez plus de mémoire et augmentez les chances de manquer le cache.

Bien sûr, si vous vous préoccupez vraiment de la performance de l'une de ces structures de données, vous devriez les tester. Vous ne devriez avoir aucun problème à trouver de bonnes implémentations de chacune d'entre elles pour la plupart des langages courants. Il ne devrait pas être trop difficile de mettre quelques-unes de vos données réelles dans chacune de ces structures de données et de voir laquelle se comporte le mieux.

1. _{Il est possible qu'une implémentation pré-alloue un tableau de nœuds, ce qui aiderait à résoudre le problème de cache. Je n'ai pas vu cela dans une vraie implémentation de listes chaînées ou d'arbres binaires (bien sûr, je n'ai pas tout vu), bien que vous puissiez certainement le faire vous-même. Vous auriez toujours une possibilité légèrement plus élevée de manquer le cache, cependant, puisque les objets <em>nœud</em> seraient nécessairement plus grands que les paires clé/valeur.}

Answer 5

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

Entre les trois choix :

Les listes chaînées sont relativement lentes pour rechercher des éléments (O(n)). Donc si vous avez beaucoup d'éléments dans votre table, ou si vous prévoyez de faire beaucoup de recherches, alors ce n'est pas le meilleur choix. Cependant, elles sont faciles à construire et faciles à écrire aussi. Si la table est petite, et/ou si vous ne faites qu'une seule petite recherche après sa construction, alors c'est peut-être le choix pour vous.

Les tables de hachage peuvent être incroyablement rapides. Cependant, pour que cela fonctionne, vous devez choisir un bon hachage pour vos entrées, et vous devez choisir une table suffisamment 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 entrées. Si vous faites une erreur, vous finirez avec un ensemble de listes chaînées vraiment coûteux et complexe. Je dirais que sauf si vous savez à l'avance à peu près quelle sera la taille de la table, n'utilisez pas de table de hachage. Cela va à l'encontre de votre réponse "acceptée". Désolé.

Cela laisse les arbres. Vous avez une option ici cependant : Équilibrer ou ne pas équilibrer. Ce que j'ai trouvé en étudiant ce problème sur du code C et Fortran que nous avons ici, c'est que l'entrée de la table de symboles tend à être suffisamment aléatoire pour ne perdre qu'un ou deux niveaux d'arbre en ne le balançant pas. Étant donné que les arbres équilibrés sont plus lents pour insérer des éléments et plus difficiles à implémenter, je ne m'embêterais pas avec eux. Cependant, si vous avez déjà accès à de belles bibliothèques de composants déboguées (par exemple : STL de C++), alors vous pouvez aussi bien utiliser l'arbre équilibré.