Listes chainées contre tables

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.

Insertion

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.

Destruction

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.

Que choisir?

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 ?

En fait, la plus grand faiblesse des tables réside essentiellement dans leur redimensionnement. Il faut alors 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, cependant 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.

Déplacer les éléments dans la table

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...

Insertion en tête ou en queue

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, l'insertion optimale consiste à 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.

Le choix dans LispE

Tout d'abord, il faut noter que LispE offre les deux représentations, il est possible de créer une liste chainée ou une table selon les besoins.

En revanche par défaut, la liste par défaut est une table.

(llist 10 20 30) ; liste chainée (linked list)
(list 10 20 30) ; liste sous la forme d'une table

Pourquoi une table?

Nous avons rapidement expliqué que les deux représentations étaient sensiblement équivalentes dans leur manipulation, alors pourquoi avoir choisi la table comme représentation sous-jacente? Surtout que ce choix n'est généralement pas celui des autres implémentations de Lisp.

La raison principale est l'accès direct à un élément.

LispE fournit de nombreuses instructions: set@, at, @ etc.qui permettent d'accéder directement à un élément selon un index:

(setq r (list 10 20 30 40))

(print (@ r 2)) ;  30

Mais cdr ou car...

car et cdr sont des instructions légendaires dans Lisp, personne ne pourrait imaginer ces langages sans ces instructions. Or, si ces deux instructions sont très simples à manipuler avec des listes chainées, il s'agit à chaque fois d'un simple parcours de pointeur, elles semblent inadaptées à des tables.

Qu'est qu'un cdr sur une table ? Une nouvelle table ?

Si c'est le cas, le parcours d'une liste deviendrait une catastrophe. On perdrait non seulement la simplicité d'un parcours de pointeurs, mais surtout on se retrouverait à chaque fois avec une copie de la table, ce qui auraient deux conséquences majeures:

1. Une consommation effrénée d'espace mémoire (duplication des tables)
2. L'impossibilité d'une manipulation locale de la liste renvoyée

La réponse

Dans LispE, le problème a été résolu en utilisant une indirection.

Plus exactement, une liste comprend deux éléments:

class LIST {
   long home;
   ITEM* items;
...

ITEM est un vecteur dont la taille peut croitre à loisir, home est l'index du premier élément dans items.

Ansi, lors d'un cdr sur un objet de type LIST, il suffit de créer un nouvel objet LIST qui partagera le même items, mais dont le home sera incrémenté de 1...

C'est un peu plus lourd qu'un parcours de listes chainées certes, mais on conserve toutes les propriétés d'accès direct à une liste, en offrant des parcours presqu'aussi performant.

De toute façon, LispE permet aussi la manipulation de listes chainées si cette approche ne convient pas.

APL

Cette représentation sous la forme d'une table des structures de base de Lisp permet en particulier l'utilisation d'opérateurs fonctionnant sur les tables (voir APL).