Un tableau DIM est bien pratique pour tenir en mémoire toutes les données d'un fichier et ce afin d'y faire des recherches, des tris, des sélections de "fiches". Quand sa taille est petite, c'est formidable, mais dès qu'il dépasse déjà quelques kilo-octets, alors on s'aperçoit que le tri alphabétique va prendre plus de vingt minutes et que la sélection de fiches devient très encombrante en mémoire... C'est vrai avec les procédés classiques, mais, en utilisant des méthodes indirectes, le même tri ne demandera plus que quinze secondes ! C'est la "ruse” de la "table d'index" que nous allons mettre en pratique ; mais avant tout il serait bon de rappeler brièvement les règles et les précautions pour créer un tableau DIM. CONSTITUTION D'UN TABLEAU DIM Il y a trois races non miscibles de DIM, ceux qui ne contiennent que des chaînes ou que des nombres réels ou que des nombres entiers. Ce dernier est le plus économique en réservation mémoire. Pour chacun de ces types, on peut avoir des tableaux à une, deux "dimensions" (rarement plus). Deux dimensions veut dire qu'il y a des lignes et des colonnes, comme un tableau sur une feuille. Une dimension, c'est la liste toute bête à une seule colonne. Trois dimensions, c'est comparable à plusieurs tableaux à deux dimensions associés. Je m'explique : deux dimensions, c'est une feuille divisée en lignes en colonnes ; préparons une liasse de quatre feuilles ainsi préparées, on a nos trois dimensions : ligne, colonne et feuillet. On peut même envisager une quatrième dimension, le numéro de la liasse (ultra-rare)... Dans le BASIC AMSTRAD, la numérotation des lignes et colonnes commence à zéro et non à un. Ainsi DIM NB(20,2) se réserve 21 lignes et 3 colonnes, soit 63 cases-valeurs/ou "cellules". Et comme il s'agit là de nombres "réels", à cinq octets chacun, il se réserve donc 63 x 5 = 315 octets, même si ce tableau reste vide. Deux octets par cases pour des nombres "entiers" (non décimaux) et trois octets pour des chaînes. Donc, seul un DIM de chaînes va augmenter de
volume lorsque l'on va le garnir (avec des chaînes de plus de trois caractères). Vous ne pouvez pas modifier ou répéter la définition d'un DIM, sinon plantage. On les déclare donc en tout début de programme, afin qu'un GOTO ne fasse pas repasser par cette ligne... En revanche, vous pouvez le supprimer, exemple ERASE NB fera oublier sa structure et son contenu (gain de place quand on n'a plus besoin d'un tableau de valeurs). Comment faire pour mettre en tableau à la fois des chaînes et des nombres ? Cas très fréquent. Deux méthodes : - Transformer les nombres en chaînes par STR$.
- Définir un second tableau DIM, numérique, où les valeurs correspondront ligne à ligne avec le tableau chaînes. C'est un peu plus lourd dans le listing, mais cela permet parfois de faire d'énormes économies d'encombrement mémoire.
Gardons la première solution pour nos exemples suivants, donc un unique tableau chaînes. Deux petites astuces : en ligne zéro, entrez (par des DATA) les légendes de vos colonnes. Pour celles qui correspondent à des STR$, faites suivre le nom par le signe dièse : PRIX #, AN #, STOCK#, etc. Ce petit repère sera utile par la suite. Vous êtes obligé de déclarer un DIM s'il y a plus de onze lignes ou colonnes. Sans DIM, vous pouvez écrire A(2,3) = 45, mais sachez qu'à votre insu l'AMSTRAD s'est aussitôt déclaré DIM A(10,10), d'où peut-être un gaspillage mémoire. LA TABLE DES INDEX Supposons que notre grand tableau soit
DIM F$(200,8). En plus, déclarons DIM S%(200), ou DIM S(200), S ayant été déclaré comme "entier" par DEFINT I-N,S. Ce DIM n'occupe donc que 201 x 2 = 402 octets. Il ne contiendra comme valeurs que des NUMEROS DE LIGNES de F$(200,8), donc ici de 0 à 200, d'où son nom de tableau ou table des index. C'est une formidable machine-outil, nous allons le prouver et ce dans absolument tous les domaines. On commence la démonstration. SELECTION DE FICHES Prenons l'exemple "bateau" d'un fichier noms-adresses. Dans la rubrique ville (colonne 6), on veut sélectionner DIJON. Il y a NF fiches au départ (NF< =200) 2020 NS = 0:' Nombre de sélectionnées
2030 FOR N = 1 TO NF 2040 IF F $ (N, 6 ) = "DIJON" THEN NS = NS+ 1 :S(NS) = N 2050 NEXTOn a répertorié dans la table des INDEX les numéros des fiches sélectionnées et on connaît leur nombre total, c'est NS. A partir de là, on peut faire n'importe quoi de cette sélection : l'enregistrer, l'afficher, la trier ou par exemple n'imprimer que les noms (colonne 1) : 3020 FOR J = 1 TO NS 3030 PRINT#8, F$(S(J), 1 ):NEXT Pour sauvegarder cette sélection : 4020 OPENOUT "DIJON.SEL" 4030 PRINT# 9,NS:' facultatif mais utile
4040 FOR J = 1 TO NS:FOR K = 0 TO 8
4050 WRITE # 9, F$(S(J),K):NEXT:NEXT
4060 CLOSEOUTSans cette table d'index, nous aurions dû, pour faire ces opérations, lancer DEUX FOIS la routine de recherche dans le DIM F$ ! LE TRI SUPER RAPIDE La technique est la suivante : 1 - On remplit DIM S avec tous les numéros de fiches, de 1 à NF. FOR I = 1 TO NF:S(I) = I:NEXT2- On lance une routine de tri sur l'une des colonnes de DIM F$, mais super important : on n'y déplace aucune fiche !! Ces comparaisons feront déplacer uniquement leurs numéros de fiches dans DIM S (des entiers de deux octets...). Donc, en fin de tri, le tableau F$ est inchangé, seul le contenu de la table des index a été bouleversé. Quel avantage ? Tout simplement que la durée du tri est environ divisée par CINQUANTE ! et parfois plus... Pourquoi ? Deux raisons à - a- Si on permutait des chaînes de F$, il faudrait chaque fois déplacer un par un le contenu de chaque colonne, par une boucle FOR NEXT supplémentaire. Donc, déjà, un gain facteur neuf,
- b- Le tri ne va déplacer que des nombres entiers, donc de deux octets chacun, plus rapides à manipuler, adresser que des rubriques de vingt caractères.
Pour un tel tableau F$, la durée du tri est de l'ordre à 1 5 à 20 secondes ! Si vous ne me croyez pas, essayez... Le fait que le tableau F$ ne bouge pas de son état "brut” est aussi un avantage car il reflète un caractère chronologique, les fiches les plus récentes étant les dernières (très utile). Comment utiliser cette table d'index triés ? Mais de la même manière que pour une sélection, en disant simplement au préalable NS = NF. Si vous voulez vraiment le tableau F$ trié, enregistrez chaque fiche dans l'ordre de la table des index (idem nos lignes 4020 à 4060). Puis, rechargez ce fichier dans DIM F$ et le tour est joué !
Notez au passage que cette même routine du tri, appliquée ici sur toutes les fiches, peut s'appliquer sans rien modifier à une liste d'index de fiches sélectionnées... Pouvoir imprimer et sauvegarder une sélection, c'est très bien, mais si en plus elle est triée c'est le super luxe, gratuit. Maintenant que nous avons exposé la stratégie générale avec la table d'index, nous allons revenir sur des détails pratiques pour les sélections et le tri. LE CHOIX DE LA RUBRIQUE A TRAITER C'est un sous-programme qui est aussi bien appelé pour une sélection, une recherche ou un tri, alors, autant faire du solide et pratique. Au début de programme, nous avons déclaré la variable NRU = nombre de rubriques-colonnes. dans notre exemple NRU = 8 (de 0 à 8 = 9 rubriques). Par des DATA, les noms de rubriques ont été entrés en ligne zéro du DIM F$. Très important, il faut que ces noms aient une lettre initiale différente, nous allons voir pourquoi. Il nous faut une page d'écran qui présente ces rubriques, une ligne sur deux pour faire plus propre, mais elles seront précédées par leur lettre initiale, caractère qu'il suffira de presser. En queue de liste, l'option Q-Quitter qui annulera l'option en cours (sélection, tri...). En début de programme, on avait défini une chaîne IR$ rassemblant ces initiales : IR$ = "":FOR I=0 TO NRU:IR$ = IR$ + LEFT$(F$(0,I),1):NEXTTout cela tient en ces trois lignes On ne présente plus le sempiternel sous-programme MENU du GOSUB 50000 qui renvoie la place K de la réponse dans TEX$. On connaît alors le numéro R de la rubrique à traiter. Si RIGHT$(F$(0,R),1 ) = " # ”, on sait qu'il s'agit de nombres et cela nous conduira à des sous-programmes de traitements complètement différents et indépendants de ceux réservés aux chaînes. RECHERCHE ET COMPARAISON DE CHAINES Dans notre exemple précédent, pour rechercher le mot "DIJON”, nous avions utilisé le signe égal. En fait, il ne faut jamais faire cela ! Vous risqueriez de louper des fiches : il faut demander si la chaîne RENFERME le mot DIJON et ce pour la fonction INSTR. LINE INPUT"Elément recherché:”,EL$ EL$ = UPPER$(EL$) IF INSTR (F$(N,R),EL$)>0 THEN...
Deux avantages :INSTR est plus rapide que la comparaison "égal” (très stricte). On trouvera une fiche comportant "DIJON CEDEX 9”, non validée par le signe égal... Si dans la rubrique prénom vous cherchez JEAN, vous allez aussi sortir les JEAN-PAUL, JEAN-PIERRE... sauf si vous avez pris la précaution de demander JEAN + un espace, d'où l'intérêt du LINE INPUT sur INPUT. Un autre type de rechèrche, souvent super pratique, est la "recherche par exclusion", c'est-à-dire les fiches ne CONTENANT PAS l'élément demandé, du genre IF INSTR(F$(N,R),EL$) = 0 THEN... Hélas, il n'est pas possible de programmer le remplacement du signe > par le signe = ; il faut tourner le problème par la fonction BASIC NOT. D'autre part, il faut signaler que nous ne voulons pas rencontrer cet EL$r alors nous le faisons précéder, dans notre LINE INPUT, par le signe "flèche en haut" (entre les touches et CLR). Pourquoi ce signe ? Parce qu'il est le symbole de NOT dans d'autres langages que le BASIC. Le listing du sous-programme qui suit est extrait d'un logiciel exploité par l'auteur. Il illustre ces différentes "manœuvres" ; il vous sera alors très facile de le modifier pour l'adapter à votre problème propre ; c'est une "base". En ligne 3070 un petit gadget "rassurant" ; en face de la rubrique choisie, un astérisque signale celle qui a été tapée, une confirmation. Autre possibilité super utile, on peut affiner la sélection par d'autres pouvant concerner d'autres rubriques, du genre VILLE contenant DIJON AND PRENOM contenant JEAN, ce qui va restreindre le nombre de fiches sélectionnées. Egalement l'option OR qui, elle, va augmenter la sélection issue de la première "passe". Le nombre de passes AND ou OR après la première sélection n'est pas limité. Nota : toutes les variables commençant par F sont des FLAGS (témoins, mouchards). Quelques éclaircissements (listing 2) : DIM LR(NRU) contient les longueurs maxi de chaque rubrique (entrées au départ par des DATA). FSEL= flag sélection ; FAJ=flag Ajout, consécutif à un passage en OR. Lignes 3130, 3150 : une condition IF mise entre parenthèses devient une "variable logique" ; égale à zéro si fausse, égale à - 1 si vraie. SELECTIONS SUR RUBRIQUES NUMERIQUES Nous aurons besoin ici d'introduire les signes <, > ou =, suivi de la valeur cible. Un exemple, rubrique CODPOS# (code postal), nous voulons sortir les fiches du Rhône : sélection en deux passes > 68999, AND, < 70000, d'où tous les codes postaux entre 69000 et 69999. OK ? Voici le sous-programme appelé par la ligne 3080 du module précédent (listing 3). LES SUPPRESSIONS DE FICHES Certains logiciels dits professionnels (par leur prix...) se contentent de vider le contenu des rubriques (fiche vide) et le nombre de fiches reste bien sûr le même. Pratique exécrable. Effacer des fiches va changer la numérotation en aval, normal, alors voici notre méthode pas du tout mathématique, mais rapide et efficace : Premier temps, la rubrique zéro de chaque fiche à effacer devient '*' , tout simplement, c'est un repère. Deuxième temps, on enregistre le tableau F$ en sautant les fiches où F$(N,0) ='*' Troisième temps, on recharge la RAM avec ce fichier écourté qui remplace donc l'ancien. Dernier temps, cet enregistrement sur disque est effacé (listing 4). Si vous n'avez qu'un lecteur de cassettes, supprimez la ligne 4690. LE TRI SUPER LUXE Nous avons déjà dit qu'il sera ultra rapide, mais il va être multi-critères, par exemple par code postal, puis par nom, puis par prénom. Là encore, le nombre de critères successifs n'est pas limité ! Afin d'augmenter la vitesse globale, nous faisons appel à deux routines de tris. La première, c'est la méthode SHELL-METZNER, ultra-rapide mais ayant le gros défaut de bouleverser l'ordre initial d'un ensemble de fiches "égales", donc inapte à un tri complémentaire. Une fois le "gros boulot" effectué par le Shell-Metzner, tri complémentaire sur les fiches égales (exemple même code postal) par "tri à bulle", plus lent mais ne perturbant pas l'ordre initial. Rappelons qu'il ne va opérer que sur des petits groupes de fiches égales rencontrés ici et là ; c'est donc bref. L'éventuel tri suivant, toujours à bulle, ne traitera que les groupes de fiches égales laissés par le tri précédent (listing 5). Si vous avez des rubriques numériques (flag FRUN = 1 ), vous devrez recopier certains modules en remplaçant les F$(...) par VAL(F$(...)), à savoir : - 5300 ' Tri 1/nombres (copie de 5200 à 5290)
- 5700 ' Tri 2/nombres (copie de 5500 à 5560)
- 5800 ' Tri égalités/nombres (copie de 5600 à 5650)
Vous saurez faire... Rappelons que ce sous-programme tri peut aussi traiter une sélection de fiches. CONCLUSION Avec un tableau DIM de 196 lignes sur 10 colonnes, nous avons chronométré 1,8 seconde pour une recherche de fiches et 21 secondes pour un tri alphabétique contre plus de quarante minutes avec un tri classique... Et pourtant vous avez vu que c'est du 100 % BASIC, mais du BASIC que l'on a pris dans le "bon sens du velours". Il n'est pas impossible que l'on puisse améliorer encore ces performances par de nouvelles petites astuces ici et là. CPC n°21 | ★ AMSTRAD CPC ★ A voir aussi sur CPCrulez , les sujets suivants pourront vous intéresser... |
CPCrulez[Content Management System] v8.7-desktop/c
Page créée en 578 millisecondes et consultée 1635 foisL'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. |
|
|
