Discussion :

[wafiwafi]

Bonjour,
J’ai lu sur un forum la question suivante et j’aimerais avoir votre avis :

Devant un contexte d’implémentation, je ne pense qu’aux tableaux et aux listes. J’ai tort, parce qu’il existe le hachage et les arbres. Pouvez-vous me dire dans quels cas dois-je y penser ? Seraient ils performants par rapport aux tableaux et aux listes tout en sachant les avantages et les inconvénients de ces deux derniers.

Ma réponse non convainquant :

Hachage : quand on n’a pas besoin de clés triés.
Arbre : quand on a une hiérarchie.
D’une manière générale, on ne peut préférer une structure de données à une autre structure qu’en présence d’un contexte précis. Exemple : préférer une liste si on a besoin de trier mais attention à sa dimension sinon, il faudra passer aux arbres.

Cette dernière citation a fait débat. Quel est donc votre avis sur tout cela.

Bien cordialement

[gangsoleil]

C'est un vieux debat.

Le hash te permet un acces en temps constant a tous tes elements (modulo les collisions), et est bien adapte pour de tres grands volumes de donnees.

Un arbre te permet d'elaguer, c'est a dire de ne pas du tout parcourir certaines branches, ce qui est pratique dans certaines recherches. Mais le temps d'acces a une donnee depend de la hauteur de l'arbre.

Les tableaux sont simples a utiliser et a conceptualiser, mais posent vite des problemes lorsque tu dois gerer des grandes tailles. De plus, tout ajout ou suppression te force a retrier tout le tableau, ce qui est vite penible (surtout que trier un tableau deja trie ne se fait pas bien avec quicksort, puisqu'on est en N2 dans ce cas).

Les listes enfin permettent facilement un parcours sequentiel, mais sont lentes a parcourir.


La ou tu as raison, c'est que c'est le contexte qui doit determiner l'utilisation de telle ou telle structure.

[souviron34]

Les listes enfin permettent facilement un parcours sequentiel, mais sont lentes a parcourir.

Et ne s'adaptent pas bien du tout par exemple à des recherches dichotomiques..

[gangsoleil]

Et ne s'adaptent pas bien du tout par exemple à des recherches dichotomiques..

Mettons pas les listes standards.

Parce qu'il y a aussi des structures plus complexes que ces 4 la, comme les listes circulaires avec des pointeurs supplementaires vers le log(N)-ieme element de la liste.
Mais si la recherche devient performante, il est necessaire que ce type de liste soit relativement statique, car si l'insertion ou la suppression d'un petit nombre d'elements (par rapport a N), il faut bien faire attention au fait que l'ajout/suppression d'un trop grand nombre d'elements implique de reparcourir toute la liste pour remettre les pointeurs vers les log(N)-ieme elements.

[souviron34]

....

A un coût du doublement ou triplement de la mémoire utilisée


Disons que oui, ça dépend entièrement du contexte...

[wafiwafi]

Merci pour vos réponses aussi pertinentes que d'habitude. Les choses sont beaucoup plus clairs et complètes comparant à ma réponse concise.
Je tiens à vous en remercier car bien du monde bénéficiera de ces savoirs.
Bien à vous