J'ai une liste chaînée d'environ 5000 entrées ("NOT" inséré simultanément), et je suis en train de parcourir la liste, cherchant une entrée particulière (mais ce n'est pas souvent), devrais-je considérer Hash Table comme plus choix optimal pour ce cas, en remplaçant la liste chaînée (qui est doublement liée & linéaire) ?? Utilisation de C sous LinuxListes liées ou tables de hachage?
Si vous n'avez pas trouvé que le code est la partie lente de l'application via un profileur, vous ne devriez rien faire pour le moment.
S'il est lent, mais que le code a été testé, fonctionne et est clair, il existe d'autres zones plus lentes que vous pouvez accélérer.
S'il est buggé alors vous devez le réparer de toute façon, optez pour la table de hachage car elle sera plus rapide que la liste. Cela suppose que l'ordre dans lequel les données sont traversées n'a pas d'importance, si vous vous souciez de l'ordre d'insertion, alors vous pouvez faire des choses avec une table de hachage et garder la commande, mais cela rendra le code beaucoup plus compliqué).
Étant donné que vous devez effectuer une recherche dans la liste seulement à l'occasion, les chances que cela soit un goulot d'étranglement significatif dans votre code est faible.
Une autre structure de données à regarder est une "liste de sauts" qui vous permet de sauter une grande partie de la liste. Cela nécessite cependant que la liste soit triée, ce qui, selon ce que vous faites, peut rendre le code globalement plus lent.
L'utilisation optimale de la table de hachage dépend du cas d'utilisation que vous n'avez pas décrit en détail. Mais plus important encore, assurez-vous que le goulot d'étranglement de la performance est dans cette partie du code. Si ce code est appelé seulement une fois de temps en temps et pas dans un chemin critique, aucune utilisation ne dérange pour changer le code.
Si vous vous souciez de la performance, vous devriez définitivement le faire. Si vous parcourez la chose pour trouver un certain élément avec une certaine régularité, ça vaudra la peine d'utiliser une table de hachage. Si c'est un cas rare, cependant, et l'utilisation ordinaire de la liste n'est pas une recherche, alors il n'y a aucune raison de s'inquiéter à ce sujet.
Avez-vous mesuré et trouvé un hit de performance avec la recherche? Un hash_map ou hash table devrait être bon.
Si vous ne faites que traverser la collection, je ne vois aucun avantage à utiliser un hashmap.
Si vous avez besoin de parcourir la liste dans l'ordre (pas dans le cadre de la recherche d'éléments, mais de leur affichage), une liste chaînée est un bon choix. Si vous ne les stockez que de manière à pouvoir rechercher des éléments, une table de hachage surpasse largement une liste chaînée (pour toutes les fonctions de hachage sauf la pire).
Si votre application requiert les deux types d'opérations, vous pouvez envisager de conserver les deux et d'utiliser la combinaison appropriée pour une tâche particulière. Le surcoût de mémoire serait faible, puisque vous auriez seulement besoin de conserver une copie de chaque élément en mémoire et que les structures de données stockent des pointeurs sur ces objets.
Comme pour toute étape d'optimisation que vous prenez, assurez-vous de mesurer votre code pour trouver le véritable goulot d'étranglement avant de faire des changements.
Je déconseille les hachages dans presque tous les cas.
Il y a deux raisons; Premièrement, la taille du hachage est fixe.
Deuxièmement et bien plus important encore; l'algorithme de hachage. Comment savez-vous que vous avez raison? comment se comportera-t-il avec des données réelles plutôt que des données de test?
Je suggère un b-tree équilibré. Toujours O (log n), aucune incertitude en ce qui concerne un algorithme de hachage et aucune limite de taille.
Qu'entendez-vous exactement par la taille du hachage? – TofuBeer
Une table de hachage est un tableau dans lequel vous indexez comme indiqué par l'algorithme de hachage. Vous ne pouvez pas modifier la taille de ce tableau, sauf si vous remappez toutes les entrées existantes. –
Quels types d'éléments stockez-vous dans cette liste? Sont-ils uniques ou non? – klew
Ils ne sont pas uniques, en fait ils sont totalement différents et leur nombre est entièrement arbitraire. – puffadder