Stockage de données
Posté le 15/07/2015 13:49
Bonjour !
Qui n'a jamais pleuré en créant une matrice remplie uniquement de 1 et de 0 ?
En utilisant deux variables pour indiquer les coordonnées d'un objet (A et B le plus souvent
) ?
La plupart du temps, nous, programmeurs utilisons plusieurs variables alors qu'une seule est suffisante. Nous le faisons car c'est plus clair et pour rendre moins lourd le programme.
Mais nous pouvons aussi nous amuser à exploiter au maximum la capacité d'une variable ! Cela sera surtout utile pour stocker des informations dans l'ordinateur de manière durable (partie II).
Dans une première partie, je donnerais deux astuces qui me plaisent pour stocker et lire rapidement deux chiffres différents dans une même variable, puis ensuite comment effectuer un "stockage de masse".
I) Le deux en un
A quoi peut servir de stocker deux informations dans la même variable ?
Le plus souvent pour les coordonnées; en deux dimensions, on a besoin d'une valeur en abscisse et d'une autre en ordonnée. A la place d'utiliser deux variables, pourquoi ne pas en utiliser une seule ?
1) Utilisation des nombres imaginaires
1) Utilisation des nombres imaginaires
Pour ce qui ne savent pas de quoi il choisit, c'est simple à comprendre
. Les mathématiciens s'arrachaient les cheveux en tentant de faire des calculs avec des racines carrés de nombres négatifs. Prenez par exemple √-3; sachant qu'un carré est toujours positif, on se rend compte que ce nombre est... impossible !
Ils ont donc décidé de créer les nombres imaginaires, des nombres non réels. √-1 correspond à i. (√3)i correspond à √-3.
Ce qui est bien avec ces nombres, c'est qu'ils ne peuvent s'ajouter avec les nombres réels. Par exemple, 2+3i ne peut pas être simplifié. On peut donc stocker deux valeurs dans une variable !
Pour des coordonnées, on peut par exemple faire correspondre l'abscisse aux réels et l'ordonnée aux imaginaires. Si un personnage doit être en bas à gauche dans un mode non-graphique, on peut entrer ses coordonnées comme suit :
1+7i→A
Mais ensuite, pour séparer l'ordonnée de l'abscisse, comment faire?
En effet, ça peut sembler difficile. Heureusement, il existe des fonctions sur votre calculatrice pour ça ! J'ai nommé ImP, qui conserve uniquement la partie imaginaire d'une variable, et ReP, qui conserve uniquement la partie réelle d'une variable. Pour positionner mon personnage, je devrais écrire :
Locate ReP A, ImP A,"o"
(Pour trouver ImP et ReP : [OPTN][F3][F6]
Note : cette technique est utilisé entre autre par
Ne0tux dans le superbe jeu
arkenstone.
Je la recommande plus que celle qui va suivre. En effet, elle est très lisible est utilisée en mathématiques ! Néanmoins, la seconde est aussi intéressante.
2) Utilisation d'un nombre décimal
2) Utilisation d'un nombre décimal
C'est plus facile à comprendre ! Pour positionner un personnage en bas à gauche, on peut aussi écrire le nombre 1,7. On utilise la fonction Int pour récupérer l'abscisse, et Frac pour récupérer l'ordonnée. Int récupère la valeur entière d'un nombre, Frac la valeur fractionnaire.
Mais Frac 1,7 renvoie 0,7...
Ce n'est pas très gênant : on notera 10Frac1,7.
Le code ressemblera à ça :
1,7->A
Locate IntA,10FracA,"o"
Vous noterez qu'on peut combiner ces deux astuces pour faire un « quatre en un ».
Imaginons : Pour un morpion, j'utilise une matrice de 3x3 cases. Si personne n'a joué sur cette case, elle contient un 0, si le joueur 1 a joué, elle contient un 1, si le joueur 2 a joué, elle contient un 2.
Plutôt que d'utiliser cette matrice, comme toutes les matrices très lourde, pourquoi ne pas utiliser juste… une variable ?
1) Méthode moyennement poussée
1) Méthode moyennement poussée
Elle est plus intuitive ; chaque case correspond à une puissance de 10. Je m'explique : imaginons que la matrice ressemble à ça :
1 1 0
0 2 2
0 0 0
La variable contiendra le nombre : 1*10⁸+1*10⁷+0*10⁶… = 110022000
En fait, c'est la même méthode que l'utilisation d'un nombre décimal, elle est cependant à plus grand échelle mais plus difficile à utiliser. En effet, pour lire la n
ieme case, on utilise la longue formule :
MOD(Int(110022000/10^(n-1)),10)
.
(tiré du tutoriel très pratique :
http://www.planet-casio.com/Fr/programmation/tutoriels.php?id=60)
Avec 9 cases, ça ne pose aucun problème. Mais une fois qu'un nombre dépasse 10^14, la calculatrice arrondis le résultat, si bien que le booléen (10^14=10^14 +1) est vrai. On a perdu une information, cette technique n'est plus suffisante. Il en faudra une plus poussée…
Je vous arrête tout de suite ; pourquoi ne pas utiliser les chaînes de caractères ?
En effet, cette technique va très bien avec ce genre de problème. Voici comment l'utiliser :
"110022000"→Str1
Exp(StrMid(Str1,A,1))
Ans contiendra la Aieme case.
On peut stocker 255 chiffres dans une chaîne de caractère, ce qui est énorme. Pas la peine d'utiliser directement un nombre. Cette deuxième partie serait-elle inutile ?
Elle ne l'est pas ; car si elle permet de stocker une grosse information de manière durable, elle ne peut pas stocker une suite de grosses informations de manière durable. Et si, à chaque fin de partie de morpion, je voulais stocker cette fin de partie ?
J'utiliserais une liste, outil le plus pratique pour stocker une suite de grosses informations. Si j'ai joué ma 78e partie, on aura Liste 1[78]=110022000.
Bien sûr, la liste 1 est très utilisé, et pour conserver ces informations on utilisera une liste peu utilisé. Pourquoi pas la liste 13 par exemple ?
2) Changer de base
2) Changer de base
Bon, récapitulons : j'espère vous avoir convaincu de l'avantage du stockage de nombres par rapport au stockage de texte. Vous venez de voir une méthode de stockage de nombre, que nous allons maintenant pousser.
Reprenez notre nombre 110022000. Vous le trouvez si bien que ça ? En fait, ce nombre est en base 3 ; chaque chiffre qui le compose est soit un 0, un 1 ou un 2. Vous vous rendez maintenant compte de l'espace perdu ? Nous devons tout de suite revenir en base 10 !
On transforme notre 1*10⁸+1*10⁷… en 1*3⁸+1*3⁷…
On obtient : 8964. Pas mal, comme réduction !
Et pour décortiquer ce 8964, comment faire?
Pour lire la n
ieme case, on fait :
MOD(Int(8964/3^(1+Int (ln 8964/ln 3)-n)),3)
Encore une fois, on peut combiner cette technique à celle des nombres imaginaires.
Voila, je ne pense pas que tout est dit sur le stockage de masse, mais c'est déjà pas mal
Si vous avez des questions, des suggestions, des remarques, des erreurs, n'hésitez pas à m'écrire !
Citer : Posté le 25/07/2015 19:05 | #
Intéressantes ces astuces
Dans les derniers tests que j'ai fait sur calcraft j'utilisais des énormes matrices mais compressées qui utilisaient les 10 chiffres de chaque case. Ça donnait quelques lignes de code pour pouvoir écrire/lire ces valeurs...
D'ailleurs, je me demande pourquoi les algorithmes qui génèrent du Super DrawStat ne le mettent pas dans une seule liste...
Quels algorithmes ? Ceux utilisés dans les programmes pour afficher des éléments tu veux dire ?
J'avais déjà plus ou moins entendu parler de la compression à Ne0 que vous avez évoqués à la première page mais je ne sais toujours pas comment/où il faisait ça :huh:
Citer : Posté le 25/07/2015 19:06 | #
Quels algorithmes ? Ceux utilisés dans les programmes pour afficher des éléments tu veux dire ?
Non, ceux qui encodent les images évidemment. PhotoCasio, Crusher ou autres...
Citer : Posté le 25/07/2015 19:24 | #
Hep Lephé !
J'suis pas d'accord, parce que sur une longue liste, en faisant ma technique on économise 2 caractères de plus sur chaque coordonnée qu'avec les imaginaires, puis moi je perd quelques octets sur la décompression, sauf que ça tu le fais une fois au début.
{1+i10,2+i11,3+i12,4+i13,5+i14,6+i15,7+i16,6+i17,5+i18,4+i17,3+i20,2+i21} //73 caractères
Aux final les octets "perdu" au bout de code de décompression sont largement récupéré lors de l'entrée des données
Citer : Posté le 25/07/2015 19:31 | #
Ah ben ça dépend de la quantité d'expressions littérales et de calculs que tu fais. Évidemment.
Si tu stockes des listes de dessin, oui. Si tu fais des calculs sur des coordonnées du plan, non.
Citer : Posté le 25/07/2015 20:03 | #
Bah moi c'était pour stoker mes 84 niveaux de Lumyce
Citer : Posté le 25/07/2015 20:16 | #
J'ai procédé comme toi Kirafi dans mon zelda
Chaque "écran" de la map correspond à une liste de ce qui s'y trouve, avec quelque chose de la forme IDXXYY : ID correspond à l'id de l'élément, X et Y aux coordonnées.
C'est assez efficace pour économiser de la place et le calcul pour décompresser n'est pas fait souvent donc ça va.
Citer : Posté le 25/07/2015 23:28 | #
Et encore remiweb tu pouvais faire IDXXY si Y<10
Enfin c'est juste une remarque je sais pas comment tu gère tout ça
Pour Lumière, j'enregistrais dans une string, et au lieu de mettre 10 pour une coordonnée je mettais A, pour 11 un B et ainsi de suite, après avec un exp() et en ayant fait un 10->A... Je récupère la bonne valeur. Ça fait économiser pas mal
Citer : Posté le 26/07/2015 02:03 | #
Je crois avoir utilisé les strings aussi pour une autre compression, et du coup je virais les virgules entre chaque coordonnées
Citer : Posté le 26/07/2015 08:40 | #
Pour Lumière, j'enregistrais dans une string, et au lieu de mettre 10 pour une coordonnée je mettais A, pour 11 un B et ainsi de suite, après avec un exp() et en ayant fait un 10->A... Je récupère la bonne valeur. Ça fait économiser pas mal
Vous manquez pas d'imagination vous autres, alors x)
Personnellement quand il s'agit de réfléchir sur du stockage binaire je suis là, mais ces astuces-là sont complètement en-dehors de mon domaine de pensée...
Je crois avoir utilisé les strings aussi pour une autre compression, et du coup je virais les virgules entre chaque coordonnées
Bonjour la décompression par contre.
Citer : Posté le 26/07/2015 15:45 | #
Et encore remiweb tu pouvais faire IDXXY si Y<10
Enfin c'est juste une remarque je sais pas comment tu gère tout ça
En vérité c'est exactement ce que je faisais, j'ai juste simplifié pour ne pas avoir à encore expliquer des détails
Dans la nouvelle version que je suis en train de faire c'est même IDXY.
J'avais aussi songé aux str, mais j'ai des éléments avec des paramètres (de la forme IDPPXY avec PP les deux paramètres) et ça rendait la décompression horrible...
Citer : Posté le 26/07/2015 15:51 | #
Si tu regarde Lumyce, j'ai fais encore pire !
Genre c'est dans une même liste (si je me souviens bien)
Et le décompresseur savais qu'on changeait d'ID de blocs car l'ID était une dixaine, et le reste des centaines, puis il s'arrêtait lorsqu'il rencontrait une unité (soit le 0 de la fin)