Tableaux de bits

Question

Bonjour tout le monde,


Je suis actuellement en train de développer une applciation qui utilise énormément d'opérations d'union (de l'ordre de 2$n$
opérations avec n un nombre variant de 70 à 1.000.000). J'ai pensé
qu'il serait judicieux d'utiliser les tabelaux de bits afin diminuer la
consommation en temps d'exécution de ces opérations. Cependant, il
existe deux catégories de tableaux de bits :

    1- La première est celle proposée dans la bibliothèque STL qui est présentée sous deux versions:

       a- les bitsets: conteneur permettant d'effectuer divers
opérations logiques (Ou, Et, Xor...etc) mais leur taille doit être
définie à travers une constante.

       b- Les vecteurs de bits "vector": J'ai remarqué
qu'elles sont moins performantes dans les     opérations logiques mais
elles offrent le fait que le nombre de bits peut être modifié à
n'importe quel moment de l'exécution du programme.

    2- La deuxième est celle proposée par la bibliothèque Boost
"dynamic_bitset": elle offre un jeux d'opérations riche afin de
manipuler avec aisance les tableaux de bits mais les performances
demeurent inférieures (d'après les stats que j'ai collecté) à celles
des variantes des tableaux de bits proposés dans STL.


Vu que les bitsets de STL offrent les meilleures performances
temporelles (les opérations logiques sont très rapides), je les ai
intégré dans mon programme. Le problème est leur taille définie par une
constante qui doit être fixe. Ceci me contraint à définir le nombre $n$
à chaque exécution dans le code source du programme, à recompiler le
tout et à exécuter.


Je me demandai si quelqu'un connait une solution afin que le programme
puisse saisir à partir de l'utilisateur le nombre $n$ et fixer la
taille des bitsets à $n$.


Merci d'avance.
SIGMA

SIGMA

acx01b · Answer

salut j'ai regardé le code asm produit par gcc pour un bitset de la STL, franchement autant faire ta propre structure façon C ça sera presque aussi clair en C, et beaucoup beaucoup plus clair dans le code asm produit !

islem1982 · Answer

J'aurais bien aimé générer ma propre classe mais toutes les tentatives que j'ai faite (C,C++) ont abouti à des classes qui sont moins performantes que celle de la STL. 

Pourrez-vous m'indiquer pourquoi à votre avis?
Ou pourrez-vous m'indiquer une classe prête qui me permettra d'implémenter efficacement les tableaux de bits dynamiques?
Merci d'avance.
SIGMA

nickydaquick · Answer

Salut , 
je me propose de t'aider avec un code vite fait 

#ifndef __TABLEAU_BITS__
#define __TABLEAU_BITS__

typedef unsigned char ubyte;
typedef unsigned int uint;

static const uint MAX_BITS = 1024;

const uint creerTableauBits(ubyte** adresse_PointeurTableau, const uint nbBits)
{
    ubyte* tablo = new ubyte[nbBits];
   *adresse_PointeurTableau = tablo;
   if(!tablo)return 0;
  return nbBits;
}

void remplacerBits(ubyte* tableau, void* donnees, uint nombreBits)
{
    int nbBitsRestantParOctet = 8;
    ubyte* ptr = (ubyte*)donnees;
   while(nombreBits--)
   {
       if(nbBitsRestantParOctet)
      {
           ++ptr;
           ++nbBitsRestantParOctet;
     }
     *tableau++ = *ptr & (0x1<<(--nbBitsRestantParOctet));
   }
}

const ubyte any(ubyte* tableau, uint nombreBits)
{
    while(nombreBits--)
        if((*tableau)++)return 1;
   return 0;
}
const ubyte none(ubyte* tableau, uint nombreBits)
{
    while(nombreBits--)
        if((*tableau)++)return 0;
   return 1;
}
const uint count(ubyte* tableau, uint nombreBits)
{
    uint size = 0;
    while(nombreBits--)size += (*tableau)++;
    return size;
}

void flip(ubyte* tableau, uint nombreBits)
{
    while(nombreBits--)(*tableau)++ ^= 1;
}
void flip(ubyte* tableau, const uint nombreBits, const uint pos)
{
    if(pos<nombreBits)tableau[pos] ^= 1;
}

void set(ubyte* tableau, uint nombreBits)
{

    while(nombreBits--)(*tableau)++ = 1;
}
void set(ubyte* tableau, const uint nombreBits, const uint pos)
{
    if(pos<nombreBits)tableau[pos] = 1;
}

void reset(ubyte* tableau, uint nombreBits)

{


    while(nombreBits--)(*tableau)++ = 0;

}

void reset(ubyte* tableau, const uint nombreBits, const uint pos)

{

    if(pos<nombreBits)tableau[pos] = 0;

}

const ubyte test(ubyte* tableau, const uint nombreBits, const uint pos)


{



    if(pos<nombreBits)return tableau[pos];
    return 0;


}

const ubyte compare(ubyte* tableau1, ubyte* tableau2, uint nombreBits)
{
    while(nombreBits--)if((*tableau1)++ != (*tableau2)++) return 1;
    return 0;
}

void operateurAND(ubyte* tableau1, ubyte* tableau2, uint nombreBits)
{//comme and tab1,tab2 le resultat est stocke dans tab1
    while(nombreBits--) (*tableau1)++ &= (*tableau2)++;
}
void operateurOR(ubyte* tableau1, ubyte* tableau2, uint nombreBits)

{//comme or tab1,tab2 le resultat est stocke dans tab1

    while(nombreBits--) (*tableau1)++ |= (*tableau2)++;

}
void operateurXOR(ubyte* tableau1, ubyte* tableau2, uint nombreBits)

{//comme xor tab1,tab2 le resultat est stocke dans tab1

    while(nombreBits--) (*tableau1)++ &= (*tableau2)++;

}

void operateurSHIFT_LEFT(ubyte* tableau,  uint nombreBits, uint nbPos, const ubyte signe)

{
    ubyte bit = ( signe?*tableau :0); //operation signee ou non

    if(nbPos<nombreBits)
    {
       ubyte* ptr = tableau+nbPos;
      uint i = nombreBits-nbPos;
      while(i--)(*tableau)++ = (*ptr)++;
      while(nbPos--)(*tableau)++ = bit;
   }
   else
        while(nombreBits--)(*tableau)++ = bit;

}

void operateurSHIFT_RIGHT(ubyte* tableau,  uint nombreBits, uint nbPos, const ubyte signe)

{
    ubyte bit = ( signe?*tableau :0); //operation signee ou non

    if(nbPos<nombreBits)

    {
       ubyte* end = tableau+nombreBits-1;

       ubyte* ptr1 = end;
       ubyte* ptr2 = ptr1-nbPos;

       uint i = nombreBits-nbPos;

       while(i--)(*ptr1)-- = (*ptr2)--;

       while(nbPos--)(*end)-- = bit;

   }

   else

        while(nombreBits--)(*tableau)++ = bit;

}

  voila . Verifiez s'il y a des erreurs, ou si j'oublies quelque chose. J'espere que ce sera assez clair et que ca donnera une idee. Salut.

 je suis heureux de faire partie d'une grande famille ...!

nickydaquick · Answer

oups j'ai oublie la fonction de destruction et la directive de fin :

void libereTableauBits(ubyte** adresse_PointeurTableau)
{
    delete [] *adresse_PointeurTableau;
    *adresse_PointeurTableau = 0;
}

#endif

 je suis heureux de faire partie d'une grande famille ...!

Tableaux de bits

4 réponses

Votre réponse

Discussions similaires