Un exercice d’algorithmique avec une table… circulaire

Pour les enseignants, les étudiants et les débutants.

Certains exercices qui traitent de la gestion d’une table me rappellent ce programme de mes débuts en 1971. À cette époque, les disques de 600 millions de caractères venaient de faire leur apparition. Une unité de disque ressemblait à un sèche-linge avec un tambour horizontal. Le disc-pack ressemblait à dix vinyles 33 tours superposés et espacés de l’intervalle nécessaire au passage des têtes de lecture-écriture.

L’accès aux informations n’était pas encore très performant. Afin d’optimiser les traitements, il était préférable que le programme aille d’abord chercher l’information en mémoire avant d’aller la chercher sur disque. Il y avait de grandes chances pour que cette information ait été déjà lue récemment. J’ai oublié le nombre d’items de la table, disons 60 pour pouvoir comparer la table au cadran d’un chronomètre mécanique à aiguille ; chaque seconde du cadran représente alors un item. Lorsque le programme avait besoin de l’information, l’objectif était donc de parcourir cette table, de l’item le plus récemment renseigné jusqu’au plus ancien avant de se résoudre à faire un accès disque et remplacer l’information de l’item le plus ancien de la table (lorsque la table était remplie) par l’information lue sur le disque.

Au début de l’exécution du programme, la table doit être progressivement alimentée jusqu’à 60. Lorsqu’il n’y a donc que trente items renseignés, par exemple, le programme parcoure la table du trentième item vers le premier et s’il ne trouve pas l’information, un accès disque renseignera le trente-et-unième item qui deviendra l’item le plus récent à partir duquel la prochaine recherche commencera.

Les soixante items renseignés, le prochain accès disque nécessaire viendra remplacer l’information du premier item. La recherche en table suivante partira par conséquent de l’item N° 1 et remontera la table à l’envers jusqu’à l’item N° 2. Etc. etc.

J’ai oublié de quelles informations il s’agissait, peut-être des communes. Pour faciliter votre réflexion, chaque item de la table serait alors composé des deux attributs :

• c_cm (code commune)
• l_cm (libellé commune)

Algorithme intéressant, non ?

Je ne vous propose pas l’algorithme programmé de cet exercice, peut-être un jour l’algorigramme si je m’ennuie un jour de pluie.

salut

c'est le principe du circularbuffer dont tu parle ?

Bonjour à tous,
Il s'agit, en effet d'un buffer circulaire.

J'ai utilisé ce principe pour une gestion de table de défaut sur une machine.
Il faut la table de n Positions, 1 pointeur de début (Vers la première donnée entrée) et un second vers la dernière de la liste.
Quand un pointeur dépasse la capacité, il suffit de le reporter un début de liste.
Si le pointeur de fin "rattrape" le pointeur de début, alors le buffer est plein et il y a risque de perte d'information.
La lecture se fait avec un troisième pointeur qui peut avancer ou reculer pour lire les données dans n'importe quel sens, idéalement en partant du pointeur de début vers le pointeur de fin.

La difficulté est plus grande si l'on souhaite pouvoir extraire des données intermédiaires car il faut, dans ce cas, "reculer" le pointeur de fin. S'il atteint le pointeur de début, alors le buffer est vide.

L'autre piste est de faire pointer une donnée vers la suivante (une chaine). La dernière pointant alors sur la première. Cette méthode permet facilement de changer la taille du buffer, en chainant le grand père au petit-fils pour supprimer le père ou en insérant un maillon.
Il faut alors mémoriser la taille du buffer. Ce buffer ne se lit que dans un sens à moins de chainer dans les 2 sens.

Belle journée à tous...

Bonjour,

Les tampons circulaires sont anciens et toujours pratiques. La tendance est de les utiliser avec des tailles n = 2^p car le modulo est très simple et efficace : un simple masquage par & M avec M = 2^p - 1 permet de se balader dans le tableau sans test. un iStart et un iiLast permettent d'avoir un 0 flottant Le tableau est plein quand iLast == (iStart - 1) & M;

Quand les volumes unitaires deviennent moindrement conséquents, les listes chainées sont intéressantes car le surcoût du chaînage devient marginal en taille. En revanche elles sont inappropriées si il y a une relation d'ordre car même si elles sont habillées comme des tableaux dans des objets bien conçus, elles restent linéaires sans réel accès direct (adieu les vraies recherches dichotomiques).

Salutations