Le Blog de SamsamTS

Classe BitArray

Je me suis posé cette question : comment minimiser la taille d'un tableau (une dimension) ne contenant que des valeurs booléennes ?
L'idée peut paraître farfelu mais prends tout son sens lors d'échanges avec une base de données.

Dans un premier temps j'ai pensé faire une simple concaténation de "0" et de "1" pour ainsi obtenir une chaine de caractères représentant le tableau.
Cependant cet solution ne me plaisait pas. C'est là que la solution me parue évidente.
Pourquoi ne pas utiliser chaque bit d'un caractère pour stocker chaque valeur du tableau ?

Oui mais voilà, le caractère 0 (valeur ASCII) est le caractère qui signifie la fin de la chaine :(
D'autres caractère peuvent être aussi problèmatique (ex : EOF)

En regardant la table ASCII de plus près on s'aperçoit que ces caractères se situes tous au début de la table. Ainsi en se passant du bit du poids le plus fort en le mettant toujours à 1 on aura des valeurs comprises entre 128 et 255 évitant ainsi tous problèmes.

Il ne restait plus qu'à créer cette classe :)

Code :

class BitArray {
   //--Private--
   private var array:Array;
   //--Constructeur--
   public function BitArray(lg:Number) {
      array = [];
      length = lg;
   }
   //--Public--
   public function get(i:Number):Boolean {
      return array[i];
   }
   public function set(i:Number) {
      array[i] = true;
   }
   public function reset(i) {
      array[i] = false;
   }
   public function serialize():String {
      var str = "";
      var strlg = Math.ceil(array.length/7);
      for (var i = 0; i<strlg; i++) {
         str += String.fromCharCode(128);
      }
      str = str.split("");
      for (var i = 0; i<array.length; i++) {
         if (array[i]) {
            var strnb = Math.floor(i/7);
            str[strnb] = String.fromCharCode(str[strnb].charCodeAt(0) | (1 << (i-7*strnb)));
         }
      }
      return str.join("");
   }
   public function deserialize(str:String) {
      array.length = str.length*7;
      for (var i = 0; i<array.length; i++) {
         var strnb = Math.floor(i/7);
         if (str.charCodeAt(strnb) != 128) {
            if ((str.charCodeAt(strnb) >> (i-7*strnb)) & 1) {
               this.set(i);
            }
         }
      }
   }
   public function get length():Number {
      return array.length;
   }
   public function set length(lg:Number) {
      if (lg>array.length) {
         for (var i = array.length; i<lg; i++) {
            array.push(false);
         }
      } else if (lg<array.length) {
         array.splice(lg);
      }
   }
}

Vos commentaires

Le dimanche 29 août 2004 à 20:41 , commentaire par thecaptain :: #

 

Salut,
Je ne comprends pas vraiment le principe de fonctionnement de ta classe  :S (surtout les 10 dernières lignes) L'idée est de stocker ton tableau (genre le sérializer) ??? car tu stocke tes valeurs dans un tableau et tu peux aussi les récupérer d'une chaine de caractère c ca ????

ps c kand que tu nous mets une balise code  :D

@++

 

Le dimanche 29 août 2004 à 21:12 , commentaire par SamsamTS :: email :: #

 

En fait l'idée c'est de pouvoir, à partir d'un tableau ne contenant que des booléen, générer une chaine de caractère qui représente ce tableau (toString). Evidemment le processus inverse doit être possible (fromString). Pour les balise de code faudra attendre un peu :-/ PS : j'ai corrigé le bug avec les < dans le code

 

Le dimanche 29 août 2004 à 22:19 , commentaire par thecaptain :: #

 

A ok je comprend mieux mnt :) En fait moi j'ai fait une interface avec comme méthode serialize(Void):String et deserilize(serializedObject:String):Void qui reviens au meme principe :) Mais avec des objets complexe.
Toutefois je ne suis pas sur qu'utiliser toString soit la bonne idée car en général on l'utilise pour 'représenter' l'objet..... enfin cela ne pause pas de problème majeurs ^^ lol
@++

 

Le dimanche 29 août 2004 à 22:37 , commentaire par SamsamTS :: email :: #

 

Tu as raison pour le toString, faudra que je change ca. L'important dans le code c'est la manipulation au niveau du bit afin de gagner un maximum de place. Par exemple si la longueur du tableau est de 14 il faudra 2 caractères pour le représenter :)

 

Le mercredi 1 septembre 2004 à 10:36 , commentaire par thecaptain :: #

 

heu samsam tu dois avoir des problèmes de code car je vois plus de retour à la ligne mais plein de < br /> qui trainent  :S

 

Le mercredi 1 septembre 2004 à 12:46 , commentaire par SamsamTS :: email :: #

 

Rah m'en parle pas je galère pour la colorisation de code. J'espère que j'arriverai à régler ca aujourd'hui.

 

Le vendredi 10 septembre 2004 à 01:55 , commentaire par fred :: #

 

je comprends pas. Tu essayes de générer des champs de bits c++ avec flash? Je t'arrête tout de suite: faut pas passer par des strings, car tu ne sais pas comment leur ressources sont allouées par le player (si? à ton avis, la taille min d'une string est de? et à chaque realloc ou malloc, la taille est incrémentée de?)
Franchement, tu as de l'idée, beaucoup de bonnes idées, alors mets-toi à un langage qui te permettra de les exploiter. Met-s toit au c, c++ ou c# (pas php, c'est une surcouche de c++, avec moins de fonctionnalités prmitives et brutales... mais plus intéressantes, surtout pour ce que tu essayes de faire).
a+

 

Le vendredi 10 septembre 2004 à 13:04 , commentaire par SamsamTS :: #

 

Non non, je n'essaye pas de reproduire les champs de bits.

Lors d'un échange de données entre flash et php les variables sont de toute facon passés sous forme de string (ou alors on m'aurait mentit ? :mrgreen: ) alors autant minimiser la taille de cette chaine dans le cas précis où toutes les valeurs du tableau sont de type booléen, surtout s'il y en a beaucoup ;)

 

Le vendredi 10 septembre 2004 à 18:22 , commentaire par fred :: #

 

alors :bravo:
Je n'avais pas penser à ça.
Par contre, tu peux peut-être passer des valeurs au php en bitcode, mais faudrait chercher loin...peut-être, 10% de chance quoi, m ais ça serait super intéressant

 

Le vendredi 10 septembre 2004 à 20:55 , commentaire par SamsamTS :: #

 

Ca serait l'idéal mais je doute que cela puisse se faire...

 

Le dimanche 19 septembre 2004 à 16:29 , commentaire par Foxy :: email :: #

 

Yo samSamTs,

d'abord bravo pour ce blog, plus y'en aura et mieux ça sera :) un lien de + dans mes favoris !

Pour ta classe, elle peut être très interessante dans le cadre d'applications multi-joueurs ou les quantités de données à transmettre peuvent avoir un bon interret à être minimisées.

Une extension possible pourrait être de sérialiser sous forme de bits un tableau de valeurs typées quelconque et que l'information sur la serialisation soit contenu dans la chaine elle même, ça permettrait ensuite de deserialiser et de retrourner le tableau de valeur original côté flash ou serveur.

Par contre, il me semble que les données transmises via les socket ou autre objets loadVars sont automatiquement converties en UTF8 (mais je me trompe peut-être), du coup est-ce que cette convertion UTF8 ne va pas casser l'intégrité de ton string !!!!

Enfin bonne idée, bon boulo en tout cas ...

 

Le dimanche 19 septembre 2004 à 20:53 , commentaire par SamsamTS :: #

 

J'y ai pensé la sérialization de valeurs quelconque, mais c'est un peut plus compliqué, mal de crâne garantit :mrgreen:

Parcontre je ne pense pas que l'UTF8 change quoique se soit, d'ailleurs il me semble que l'encodage des string dans flash est déjà en UTF8, de toute facon les normes d'encodage ce n'est que pour l'affichage, du moment que la valeur au niveau du bit reste inchangée il n'y a pas de soucis.

 

Le dimanche 19 septembre 2004 à 23:17 , commentaire par Foxy :: email :: #

 

Oui tu as raison, au niveau de ton implémentation ça ne changera strictement rien tant qu'elle est utilisée sous flash.

Par contre ce que tu penseras être un '233 base 10' en bits justement se retrouvera codé sur 2 octets en sortie de flash (car 233 ='é', et 'é' et codé sur 2 octets en UTF8). Enfin bref, ne pas considérer que ton tableau est un tableau de bit sûr ! c'est un String sûr (qui peut être interprétté comme bits). ça peut être confusant si tu traites avec d'autres applications tierces seulement.

 

Ajouter un commentaire