Les files

Retirer la première de 1000 valeurs d'un tableau JavaScript avec shift déplace les 999 autres ; un tampon circulaire fait le même travail en une étape.

Premier entré, premier sorti

Une file, c'est une file d'attente devant un comptoir. Les gens arrivent par l'arrière et sont servis par l'avant : celui qui est arrivé en premier repart en premier. La règle est premier entré, premier sorti (FIFO en anglais). Les deux opérations sont enfiler (enqueue), qui ajoute une valeur à l'arrière, et défiler (dequeue), qui retire la valeur de l'avant. Dans les notes du cours 6.006 du MIT, une file est l'interface de séquence limitée à insert last(x) et delete first().

Les files sont partout où il faut traiter des tâches dans l'ordre d'arrivée : documents en attente d'une imprimante, touches en attente d'un programme, messages en attente d'un serveur. Le parcours en largeur, vu dans le cours d'algorithmique, garde dans une file les cases qu'il lui reste à visiter, et c'est exactement pour cela qu'il explore par anneaux à égale distance.

La solution facile et son coût caché

En JavaScript, la file évidente est un tableau : push pour enfiler à l'arrière et shift pour défiler à l'avant. Ça marche, et pour des files courtes, c'est très bien. Mais regarde ce que fait shift. MDN indique qu'il « décale toutes les valeurs de 1 vers la gauche », et la spécification ECMAScript l'écrit comme une boucle qui copie l'élément k à la position k − 1 pour chaque k. Le début d'un tableau est le côté coûteux, comme l'a montré la première unité. Défiler une file de n valeurs coûte 1 lecture plus n − 1 déplacements : une file de 1000 valeurs coûte donc 1000 étapes par défilement. (Les moteurs peuvent utiliser des raccourcis en interne, mais la spécification ne promet rien.)

Si tu enfiles 5 valeurs dans un tableau vide puis que tu les défiles toutes les 5, les enfilements coûtent 5 étapes et les défilements 5 + 4 + 3 + 2 + 1 = 15, soit 20 en tout. L'essentiel de ce travail consiste à déplacer des valeurs qu'on ne retire même pas.

Ne pas déplacer les valeurs, déplacer l'avant

La solution consiste à ne plus déplacer les valeurs et à retenir plutôt où se trouve l'avant. On garde un indice appelé head. Défiler lit la valeur à head et ajoute 1 à head ; rien d'autre ne bouge. Le problème, c'est que les cases avant head sont perdues. Un tampon circulaire (ring buffer) les réutilise : le tableau a un nombre fixe de cases, disons 8, et les positions font le tour, si bien que la case après 7 est 0. On stocke head et size. L'enfilement suivant va dans la case (head + size) mod 8, et un défilement prend la case head et fait passer head à (head + 1) mod 8. Les deux opérations coûtent 1 étape. Le prix à payer est une capacité fixe : quand size atteint 8, la file est pleine, sauf si l'on recopie tout dans un anneau plus grand comme le ferait un tableau dynamique.

Laquelle utiliser ? Pour une file qui ne contient jamais plus de quelques dizaines de valeurs, push et shift sont courts et clairs, et les déplacements ne coûtent presque rien. Pour une file par laquelle passent des milliers d'éléments, comme les cases d'un grand parcours en largeur, un indice head ou un tampon circulaire maintient chaque défilement à une étape, et la différence augmente avec la longueur de la file.