On est d'accord qu'il y a mieux "en général" qu'une liste simplement chaînée, par exemple des listes de tableaux. Mais il n'y a pas de structure qui soit bonne "en général", et qui permette d'éviter de se demander quoi choisir. Si ça existait, tu penses bien que tout le monde l'utiliserait :)
L'approche la plus propre que je connaisse est celle de la STL, où effectivement dans de nombreux cas on peut changer la structure de données sans changer le code, mais là non plus on n'est pas dispensé de savoir choisir entre les différents types de données. Et si tu choisis le mauvais type et que tu fais un algo en fonction de ce type, tu devras quand même réécrire ton code si tu changes d'avis.
Ce que je veux dire, c'est que tu peux abstraire autant que tu veux tes types de données, au moment de coder l'algo tu es obligé de savoir des choses basiques comme:
- Je peux parcourir mes éléments séquentiellement ou pas ?
- Je peux accéder à un élément n'importe où ou pas ?
- Je peux parcourir dans les deux sens, ou dans un seul ?
- Je peux déplacer des éléments ou pas ?
- Je peux stocker beaucoup de données ou pas ?
(Pour toutes ces questions, il faut bien sûr penser "en temps et en espace raisonnables", sinon la réponse est toujours oui)
Et même si ton API te fournit le même ensemble de fonction pour tous les types, ça ne veut pas dire que ces fonctions sont efficaces.
Par exemple si tu utilises comme abstraction des iterateurs, ton API ne te donnera pas d'iterateur qui puisse se déplacer dans les deux sens pour une liste simplement chaînée. Ou bien si elle te fournit un iterateur qui le fait, il sera très lent.
Pareil pour les listes doublement chaînées, tu auras sûrement une fonction "obtenir l'élément à la position i", mais cette fonction sera lente. Donc si tu veux être efficace, quoi qu'il arrive, tu devras connaître les limites du type de données que tu manipules.
(Après, savoir si ça vaut le coup de se casser la tête pour choisir le bon type de données, c'est un autre problème. Dans beaucoup de cas, utiliser un Vector en Java sera très acceptable. Mais si tu as besoin d'être efficace, pas le choix)
[^] # Re: autre optimisation
Posté par Yusei (Mastodon) . En réponse au journal Vous trouvez GNOME lent ?. Évalué à 3.
L'approche la plus propre que je connaisse est celle de la STL, où effectivement dans de nombreux cas on peut changer la structure de données sans changer le code, mais là non plus on n'est pas dispensé de savoir choisir entre les différents types de données. Et si tu choisis le mauvais type et que tu fais un algo en fonction de ce type, tu devras quand même réécrire ton code si tu changes d'avis.
Ce que je veux dire, c'est que tu peux abstraire autant que tu veux tes types de données, au moment de coder l'algo tu es obligé de savoir des choses basiques comme:
- Je peux parcourir mes éléments séquentiellement ou pas ?
- Je peux accéder à un élément n'importe où ou pas ?
- Je peux parcourir dans les deux sens, ou dans un seul ?
- Je peux déplacer des éléments ou pas ?
- Je peux stocker beaucoup de données ou pas ?
(Pour toutes ces questions, il faut bien sûr penser "en temps et en espace raisonnables", sinon la réponse est toujours oui)
Et même si ton API te fournit le même ensemble de fonction pour tous les types, ça ne veut pas dire que ces fonctions sont efficaces.
Par exemple si tu utilises comme abstraction des iterateurs, ton API ne te donnera pas d'iterateur qui puisse se déplacer dans les deux sens pour une liste simplement chaînée. Ou bien si elle te fournit un iterateur qui le fait, il sera très lent.
Pareil pour les listes doublement chaînées, tu auras sûrement une fonction "obtenir l'élément à la position i", mais cette fonction sera lente. Donc si tu veux être efficace, quoi qu'il arrive, tu devras connaître les limites du type de données que tu manipules.
(Après, savoir si ça vaut le coup de se casser la tête pour choisir le bon type de données, c'est un autre problème. Dans beaucoup de cas, utiliser un Vector en Java sera très acceptable. Mais si tu as besoin d'être efficace, pas le choix)