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 15/07/2015 21:11 | #
Bravo ! Je sais pas si tu as trouvé ça tout seul Programateur, mais ça va m'aider.
En fait, j'ai travaillé sur un pendu qui enregistre les mots nouveaux dans un dictionnaire. C'est en voulant rendre le dictionnaire de plus en plus performant que je suis arrivé à ces techniques ! Mais j'avoue que sans tous les tutos de planet casio, j'aurais eu du mal !
J'ai voulu être honnête et je remercie particulièrement Ne0tux pour son astuce des nombres imaginaires, qui ouvrait la voie à une série d'astuce pour "gratter" de la place
Citer : Posté le 15/07/2015 21:30 | #
Les imaginaires ne "grattent" pas de la place ><
Ça simplifie le stockage des points, mais c'est tout.
Citer : Posté le 18/07/2015 14:59 | #
Oui ok
Citer : Posté le 18/07/2015 18:11 | #
Après en terme d'espace occupé dans le programme pour l'accès à la donnée c'est peut être plus léger que l'accès à une liste à un certain indice non ? (Je pose la question juste
Citer : Posté le 18/07/2015 20:29 | #
remplir une liste de 1 et une autre de i est plus lourd que de remplir une liste de 1+i
Citer : Posté le 18/07/2015 21:21 | #
En terme de code, non.
List1+List2 est plus léger que ReP List1+ImP List1.
D'ailleurs toutes ces méthodes sont coûteuses en taille de bytecode.
Citer : Posté le 18/07/2015 21:58 | #
C'est ce que je dis, c'est pratique pour simplifier la gestion des coordonnées : 3 + 2i -> A est bien plus simple à trimbaler et gérer que 3 ->A ; 2->B
Et puis quand il faut faire bouger c'est plus simple aussi : A + 1 + i -> A
Mais oui, niveau poids global, ça en prend souvent plus que deux variables différentes.
Citer : Posté le 18/07/2015 22:58 | #
ImP et ReP prennent pas 2 octets en plus ?
Citer : Posté le 19/07/2015 00:02 | #
C'est le cas. D'où les programmes plus gros.
Citer : Posté le 19/07/2015 08:46 | #
Cette méthode est intéressante mais Est-ce plus rapide de l'utiliser que de faire par exemple :
A+2→A
B+3→B
Citer : Posté le 19/07/2015 09:03 | #
Si A vaut 3 + 2i à la base, alors à la fin il vaut 4 + 3i. À mon avis, cette instruction de Darks est une référence à un déplacement en diagonale dans un repère en deux dimensions (+1 sur x et +1 sur y).
Mais en prenant compte de ReP et ImP, c'est toujours plus rentable d'utiliser des variables normales. Toutes les méthodes ici sont désavantageuses en terme de bytecode.
Citer : Posté le 19/07/2015 10:53 | #
Pour les coup les complexes deviennent avantageux lorsqu'il faut modifier les points : exemple d'une rotation d'angle T(heta) et de centre O(mega) :
(A-O)e^(iT)+O->A
Idem pour les homotécies telles que les symétries, etc.
Citer : Posté le 19/07/2015 11:04 | #
Moi, pour mes programmes, je combine les 2.
Je sais cela prends donc 3 fois plus de place
PM Générateur
graph100+ bleue
Neuronix9302
2nde GT
Citer : Posté le 19/07/2015 18:55 | #
Pour les coup les complexes deviennent avantageux lorsqu'il faut modifier les points
Tu marques un point.
Déjà que les complexes sont là pour ça... ^^'
Citer : Posté le 19/07/2015 18:56 | #
Ouh, ça devient difficile à suivre, déjà que c'est complexe, faut pas que ça devienne imaginaire
Citer : Posté le 19/07/2015 18:59 | #
Ouh, ça devient difficile à suivre, déjà que c'est complexe, faut pas que ça devienne imaginaire
Citer : Posté le 19/07/2015 19:07 | #
Citer : Posté le 25/07/2015 16:54 | #
Bah moi dans Lumyce je stockais pas comme ça Y+iX→A , ni Y.X→A, mais YX→A !
Pourquoi ? Bah ça prend 3 caractères dans le code alors que les autre 5 avec les imaginaires et 4 pour les décimaux
Exemple Y=4, X=19
4+i19→A
4.19→A
419→A
Puis la décompression :
Y = Int(A÷100)
X = Mod(A, 100) ou X = 10Frac(A÷100)
Citer : Posté le 25/07/2015 17:10 | #
Bah moi dans Lumyce je stockais pas comme ça Y+iX→A , ni Y.X→A, mais YX→A !
Il faut mettre une barre au-dessus de YX, sinon mathématiquement tu parles du produit... ^^' (j'ai cru, j'ai flippé une seconde)
Au passage t'as mis X=19 mais utilisé X=18. Enfin.
C'est vrai qu'on est toujours prêts pour grapiller un octet de notation, hein !
Mais c'est pas si rentable. Regarde :
Int(A÷100)→Y
Mod(A,100)→X
100Y+X→A
[b]Total : 31 octets[/b]
ReP A→Y
ImP A→X
Y+iX→A
[b]Total : 23 octets[/b]
Je suis pas convaincu encore.
Citer : Posté le 25/07/2015 17:58 | #
Merci Lephenixnoir ! Défendons les complexes !
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: