bitset! & compagnie

bitset! & compagnie
guest2	16-Jan-2008/18:05:51+1:00
En regardant sur le wiki les dernières évolutions du format bitset! pour la R3 (http://www.rebol.net/wiki/Bitsets) Je m'aperçois avec effroi que j'ai sous estimé la puissance de ce type de donnée depuis des années. Tout le monde connait son usage pour faire du parsing de strings mais on peut faire bien d'autres choses encore et pour le reste, il y a Eurocard-Mastercard gérer des listes d'entiers (sans répétition de valeur): ========================== Imaginons devoir gérer une liste d'entiers. La façon la plus commune est d'utiliser un block. [1 5 10 102 ...] hors il faut savoir (si mes informations sont exactes) que n'importe quelle type de donnée dans un block occupe au minimum 16 octets en mémoire (je sais c'est beaucoup, même pour un char!) ainsi pour coder le block [1 50 10] Rebol alloue 32 octets pour le block lui même et 16 octets par entier, ce qui fait un total de: 32+163 = 80 octets argh!!!!!!! Maintenant la même chose avec un bitset! Tout d'abord, il faut connaitre la valeur maximale que peut contenir le bitset. Fixons la à 100 pour commencer. Un bitset doit avoir une longueur qui est mutiple de 8, donc pour 100 on a: make bitset! 104 La mémoire allouée par Rebol pour ce bitset est de 32 octets fixes (à vérifier) + la taille du bitset! divisé par 8, soit: 32 + (104/8) = 45 octets ensuite pour insérer les valeurs dans le bitset il suffit de faire: >>insert b 1 >>insert b 50 >>insert b 10 Pour stocker ces 3 entiers, Rebol fait la chose suivante: il utilise la valeur de l'entier pour calculer la position d'un bit dans le bitset puis il le positionne à 1. Oui vous avez bien lu, chaque entier consomme 1 SEUL bit en mémoire. Mais cela signifie aussi que le bitset ne peut pas contenir plusieurs fois la même valeur. Donc résumons, au niveau de la consommation mémoire pour savoir si il vaut mieux utiliser un bitset ou un block d'entiers, il faut prendre en compte les paramètres suivant: - Le nombre maximal d'entiers contenus dans la liste: N - La valeur de l'entier le plus grand qui peut être stocké dans la liste: V Si V/8 < N16 alors il faut utiliser un bitset Notez que si vous utlisez des list! ou des hash! d'entiers alors le déséquilibre en faveur des bitsets est encore plus important. Dans ce cas, il n'y a même pas à calculer, il FAUT utiliser un bitset. Mais ce n'est pas tout... Manipulation des bitsets ======================== La seconde raison qui peut vous faire choisir un bitset plutôt qu'un block d'entier, c'est la rapidité des opérations de manipulation. * Recherche d'une valeur dans un bitset Dans R2, la recherche se fait avec find (ex: find b 1) Une recherche dans un bitset sera TOUJOURS beaucoup plus rapide qu'une recherche dans un block, une list! et même un hash! Mieux, la taille du bitset n'influe quasiment pas sur la performance. * Ajout d'une valeur dans un bitset Dans R2, l'insertion se fait avec la func insert (insert b 10) Même remarque que pour la recherche au niveau de la performance. Un second avantage c'est qu'il n'est pas nécessaire de tester si la valeur existe déjà pour l'insérer. On peut très bien faire successivement: >>insert b 2 >>insert b 2 >>insert b 2 La valeur 2 ne sera présente qu'une seule fois, cela interdit les répétitions de valeurs mais l'avantage c'est qu'on a pas à tester si la valeur s'y trouve déjà avant de l'insérer car la VM ne produit aucune anomalie. * Suppression d'une valeur dans un bitset Là il y a un petit problème dans R2, pas de fonction native pour ça (enfin j'ai pas trouvé) mais dans R3 on pourra, cool !!! Heu-reu-se-ment il y'a findus !!! On peut quand même se démerder en passant par une représentation temporaire en binary!. remove-bitset: func [b val /rmv][ rmv: clear copy b insert rmv val to bitset! and~ to binary! negate rmv to binary! b ] L'inconvénient de cette fonction c'est qu'elle renvoie un nouveau bitset! au lieu de simplement le modifier. Si y'en a qu'on d'autres idées plus simples, je suis preneur... Résumons ******** Les bitsets d'entiers permettent à la fois un gain de mémoire et des performances accrues pour la recherche et l'ajout. On peut aussi l'utiliser avantageusement à chaque fois qu'on veut gérer des listes de flags (comme dans les faces) même si cette proposition meriterait d'avantage de développement (peut-être une autre fois) Il y'a d'autres applications à envisager, comme une fonction de recherche ultra-rapide multi-critère sur de grosses quantitées de données grace à la constitution d'index de table au format bitset. Enfin bref, on nouveau monde s'ouvre...
DocKimbel	16-Jan-2008/22:32:51+1:00
Pour supprimer une entrée dans un bitset en R2 (cad la passer à 0), il est possible d'utiliser REMOVE mais avec le rafinement /PART : >> a: make bitset! 104 == make bitset! #{00000000000000000000000000} >> insert a 50 == make bitset! #{00000000000004000000000000} >> remove/part a 50 == make bitset! #{00000000000000000000000000}
guest2	16-Jan-2008/23:25:18+1:00
heu-reu-seu-ment il y a le Dock ! Bravo Dock et merci J'avais effectivement mal cherché car on en a parlé dans la mailing list. http://www.rebol.org/cgi-bin/cgiwrap/rebol/ml-display-thread.r?m=rmlLKCJ Bon avec ce remove/part, il n'y a plus aucune excuse pour ne pas utiliser les bitsets d'entiers. (positifs aurais-je du préciser)
Login required to Post.