-
Notifications
You must be signed in to change notification settings - Fork 8
2.6 Une implantation tabulaire
Tous les langages de programmation offrent des listes sous une forme ou une autre elles sont au coeur de nos algorithmes. Dans certains langages comme Python ou C, les listes sont naturellement implantées sous la forme de table dont la dimension est fixe. Une table est une séquence continue de cases mémoires dans lesquelles nos valeurs numériques ou autres sont rangées. Dans le cas de Python, cette table peut automatiquement s'étendre pour accepter de nouveaux éléments. Mais elle reste fondamentalement une table dans laquelle les éléments sont directement accessibles via leur index.
Lisp traditionnellement manipule des listes chainées. Au lieu d'un accès direct via un index, une liste chainée doit être parcourue élément par élément pour parvenir à la place précise qui nous intéresse.
Lorsque l'on oppose les deux représentations, on met souvent en avant la facilité avec laquelle on peut insérer un élément dans une liste chainée, une opération qui consiste à manipuler un ou deux pointeurs en un temps fixe. Dans le cas d'une table, cette opération peut s'avérer très coûteuse, puisqu'il faut d'abord déplacer tous les éléments vers la droite pour libérer une case où ranger cet élément. Même l'ajout en bout de table peut s'avérer catastrophique si l'espace réservé par la table est trop petit. Il faut alors réallouer un espace plus grand et y recopier l'ensemble de la table, sans oublier de détruire l'espace précédent.
De la même façon, la destruction d'un élément dans une liste chaînée se résume à une simple réorganisation des pointeurs, là aussi une opération très simple qui prend un temps fixe. Dans le cas d'une table, il faudra aussi déplacer tous les éléments vers la gauche pour éviter de laisser trop de trous dans la représentation finale.
Puisque chacune de ces actions, insertion ou destruction, prend un temps fixe, il semble évident que la liste chainée est de loin la plus efficace, n'est-ce pas ?
La plus grand faiblesse des tables réside essentiellement dans leur redimensionnement, quand elle n'offre plus assez de place. Là, il faut créer un espace plus grand, y recopier nos éléments et détruire l'espace précédent. Ces manipulations semblent horriblement coûteuses en temps et en mémoire. Elles le sont, mais il existe des méthodes d'allocation qui réduisent considérablement ces redimensionnements. En particulier, on peut décider de multiplier l'espace par deux à chaque fois.
J'en vois certains affirmer que le fait de devoir réarranger les éléments dans la table lors d'une insertion ou une destruction pose aussi problème, alors que dans une liste, il suffit simplement de réorganiser deux pointeurs.
Ce que souvent les gens oublient, c'est que pour manipuler un élément, il faut se positionner dessus. Dans une table, l'index suffit pour se positionner directement sur un élément, dans une liste, il faut parcourir tous les pointeurs jusqu'à tomber sur l'élément en question.
En réalité, les deux opérations sont équivalentes: se déplacer de pointeur en pointeur ou recopier un élément d'une case à l'autre, ça prend généralement le même temps...
L'insertion optimale d'éléments obéit évidemment à des règles différentes selon les structures de données:
Dans le cas d'une liste chainée, les manipulations optimales consistent à insérer en tête de la liste, ce qui évite des parcours coûteux. Dans le cas d'une table, l'ajout en queue est optimal, puisqu'il évite de devoir déplacer tous les éléments pour libérer une place.