Tableaux de bits

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<bool>": 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

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 !

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

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 ...!

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 ...!