APPLICATIONSDIVERS ★ LE CLASSEMENT INSTANTANE PAR SUBSTITUTION ★

Le classement instantané par substitutionApplications Divers

Vous avez certainement étudié toutes les méthodes de tri, et vous voilà devant votre clavier patientant que les interminables boucles imbriquées classent quelques malheureux tableaux ou fiches.

L'auteur de ces lignes vous invite à oublier tout cela car, a moins d'avoir à classer des nombres astronomiques à la neuvième décimale près, en pratique vous n'en avez nullement besoin.

Que trie-t-on dans la vie courante ? La plupart du temps, on trie des nombres entiers représentant une quantité ou une propriété quelconque.

Pourtant ces nombres étant naturels, ils occupent une place naturelle dans leur ensemble.

C'est l'idée de base : il suffit de remplacer le doute que comporte chaque tri par la certitude du classement naturel, en substituant la référence à la valeur. Tapez les quelques lignes du listing n° 1 et lancez le programme.

Les nombres entiers aléatoires, de 0 à 100 sont imprimés dans l'ordre de leur apparition et classés instantanément dans le tableau A à l'indice égal à leur valeur (ligne 10). C'est tout, le tri est terminé !

Il suffit maintenant de les imprimer (ou de les empiler dans le même tableau, la libération des places étant plus rapide que l'occupation de fait des trous).

En prenant l'indice de boucle croissant, l'ordre sera croissant et inversement. Cette fois c'est la valeur qui est égale à l'indice et le contenu du tableau, contrairement à tous les autres types de tri, ne contient pas la valeur, mais le nombre de valeur identique, ou le zéro en l'absence d'une valeur.

Ainsi, dans l'exemple n° 1, le zéro apparaît deux fois, le un quatre fois, alors que 4, 5 et 7 n'existent pas, etc.

En pratique il ne suffit pas de classer les valeurs, il faut savoir, aussi à quoi elles correpondent.

Un marchand de chaussures, par exemple, ayant une centaine de modèles, veut savoir combien de paires il lui reste de chaque modèle et ceci dans l'ordre croissant afin de voir quels sont les modèles qui arrivent à épuisement.

Modifier le programme selon le listing n° 2.

Cette fois les références (numéros des modèles) seront classées en même temps que les valeurs et à l'indice = valeur.

A l'impression, les valeurs sont accompagnées de leur référence (exemple n° 2).

Pour les nombres entiers, il suffit de connaître la plus grande valeur possible, afin de dimensionner le tableau en conséquence, mais on peut, aussi, se passer de tableaux (listing n° 3). Toutefois en basic cette méthode est moins rapide que celle du listing n° 1 : pour 4000 nombres, temps d'impression inclus, 2 minutes 34 secondes pour la méthode de tableau, contre 3 minutes 28 secondes pour "POKE".

On peut classer de même manière et aussi rapidement les nombres décimaux. Il faut fixer la précision nécessaire (dans la vie courante deux décimales derrière la virgule). Utilisez le listing n° 4 (exemple n° 3).

Pour les nombres négatifs, il faut diviser le tableau en deux parties égales, le zéro étant au milieu (listing n° 5 et exemple n° 4).

On peut conclure que ce type de classement n'est limité que par la taille de la mémoire, mais ceci est valable pour tous les programmes opérant sur tableaux. Les personnes possédant un lecteur de disquettes peuvent concevoir des fichiers "DATA" indicés et augmenter encore les possibilités.

Pour les autres, moins favorisés, voici une manière d'augmenter la capacité : le classement synoptique par substitution des coordonnées (listing n° 6).

Le programme du listing n° 7 fait le classement de 120 320 valeurs comprises entre 0 et 120319 (sans références).
Durée : 1 heure, 29 minutes environ. Mais soyons réalistes, ceci n'est qu'une démonstration.

Le dernier listing (n° 8) est destiné aux heureux possesseurs du CPC 6128 ou d'une extension de mémoire. Il exploite les 64K octets de mémoire supplémentaire, grâce à l'utilitaire "BANKMAN". Ainsi seul l'index (tableau A) et le programme lui-même occupent la mémoire programmable. Ceci permet d'incorporer ces quelques lignes à un programme d'application particulière, selon chaque usager. Les valeurs sont codées par enregistrement. Chaque enregistrement comporte la totalité des éléments possibles codés sur 1 bit. A la lecture des résultats seuls sont lus les bits mis à 1 et ceci uniquement pour les octets transformés par "bin$" dont au moins un bit est mis à 1. L'accès à chaque enregistrement est direct aussi bien à l'écriture qu'à la lecture. Dans ce dernier cas seuls sont lus les enregistrements non "nuls" grâce à l'index (tableau A).

Pour tous ces petits programmes, compte-tenu de la lenteur d'impression on se rend difficilement compte de la vitesse réelle de classement. Si l'impression ne vous est pas utile au moment du tri, supprimez-là.

Il est bien évident que tous ces programmes traduits en langage machine gagneront encore en rapidité.

En réalité, il est plus pratique d'adapter un petit programme en fonction du cas traité, ainsi les méthodes les plus simples seront les plus rapides. Et n'oubliez pas que le même principe peut être appliqué aux chaînes de caractères.

CPC n°19

★ EDITEUR: CPC Revue
★ ANNÉE: 198x
★ CONFIG: 128K + AMSDOS + BANKMAN
★ LANGAGE:
★ LICENCE: LISTING
★ AUTEUR: D. Vasiljevic

★ AMSTRAD CPC ★ DOWNLOAD ★

Je participe au site:
» Newfile(s) upload/Envoye de fichier(s)
★ AMSTRAD CPC ★ A voir aussi sur CPCrulez , les sujets suivants pourront vous intéresser...

Lien(s):
» Coding Src's » Sound - Reflexion Rag
» Coding Src's » 3D Graf
» Coding Src's » Rotating Polygons (Computing with the Amstrad)
» Coding Src's » Graphic Patterns
» Coding Src's » Pythagorasbaum (CPC Amstrad International)
» Coding Src's » Pi - Petr Potuznik (CPC Amstrad International)

QUE DIT LA LOI FRANÇAISE:

L'alinéa 8 de l'article L122-5 du Code de la propriété intellectuelle explique que « Lorsque l'œuvre a été divulguée, l'auteur ne peut interdire la reproduction d'une œuvre et sa représentation effectuées à des fins de conservation ou destinées à préserver les conditions de sa consultation à des fins de recherche ou détudes privées par des particuliers, dans les locaux de l'établissement et sur des terminaux dédiés par des bibliothèques accessibles au public, par des musées ou par des services d'archives, sous réserve que ceux-ci ne recherchent aucun avantage économique ou commercial ». Pas de problème donc pour nous!

CPCrulez[Content Management System] v8.7-desktop/cache
Page créée en 133 millisecondes et consultée 431 fois

L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.