Bit tableau en C ++

Question

Lorsque vous travaillez avec des problèmes du projet Euler j'ai besoin souvent de grande taille (> 10 ** 7)

de tableau de bits.

Mon approche normale est l'un:

bool* sieve = new bool[N];

bool sieve[N];

Lorsque N = 1.000.000 mon programme utilise 1 mégaoctet (8 * 1000000 bits).

Y at-il une façon plus efficace d'utiliser des tableaux de bits de stockage que bool en c ++?

Answer 1

Utilisez std::bitset (si N est une constante) en utilisant par ailleurs que d'autres std::vector<bool> ont mentionné (mais n'oubliez pas de lire cet excellent article par Herb Sutter)

  

A bitset est une classe spéciale de conteneur qui est conçu pour stocker des bits. (Éléments avec seulement deux valeurs possibles: 0 ou 1, vrai ou faux, ...)

     

La classe est très similaire à un réseau régulier, mais l'optimisation de l'allocation de l'espace : chaque élément occupe un seul bit (ce qui est huit fois moins que le plus petit type élémentaire en C ++: char).

EDIT :

Herb Sutter (dans cet article) mentionne que

  

La raison std :: vector est non conforme est qu'il tire des tours sous les couvertures pour tenter d'optimiser l'espace: Au lieu de stocker char complet ou int pour chaque bool [1] (en prenant au moins 8 fois l'espace, sur les plates-formes avec caractères 8 bits), il emballe les bools et les stocke sous forme de bits individuels (à l'intérieur, par exemple,) dans sa caractères représentation interne.

     

std :: vector forces une optimisation spécifique sur tous les utilisateurs en l'inscrivant dans la norme. Ce n'est pas une bonne idée; différents utilisateurs ont des exigences différentes, et maintenant tous les utilisateurs du vecteur doivent payer la pénalité de performance même si elles ne veulent pas ou ont besoin des économies d'espace.

EDIT 2 :

Et si vous avez utilisé Boost vous pouvez utiliser boost::dynamic_bitset (si N est connu lors de l'exécution)

Answer 2

Pour le meilleur ou pour le pire, std::vector<bool> utilisera bits au lieu de celui des booléens, pour économiser l'espace. Donc, il suffit d'utiliser std::vector comme vous auriez dû être en premier lieu.

Si N est une constante , vous pouvez utiliser std::bitset.

Answer 3

type A 'bool' ne sont pas stockées en utilisant uniquement 1 bit. De vos commentaires sur la taille, il semble utiliser 1 octet entier pour chaque bool.

A C comme façon de le faire serait:

uint8_t sieve[N/8]; //array of N/8 bytes

et logique OU octets ensemble pour obtenir tous vos morceaux:

sieve[0] = 0x01 | 0x02; //this would turn on the first two bits

Dans cet exemple, 0x01 et 0x02 sont des nombres hexadécimaux qui représentent octets.

Answer 4

Vous pouvez consulter std::bitset et std::vector<bool>. Ce dernier est souvent recommandé contre, parce que, malgré l'vector au nom, il n'agit pas vraiment comme un vecteur de tout autre type d'objet, et en fait ne satisfait pas aux exigences d'un récipient en général. Néanmoins, il peut être très utile.

OTOH, rien ne va (au moins fiable) magasin de 1 million de valeurs bool en moins de 1 million de bits. Il ne peut simplement pas être fait avec certitude. Si vos jeux de bits contiennent un degré de redondance, il existe plusieurs schémas de compression qui pourraient être efficaces (par exemple, LZ *, Huffman, l'arithmétique) mais sans une certaine connaissance du contenu, il est impossible de dire qu'ils seraient pour certains. Chacune de ces aura cependant stocker normalement chaque bool / bit dans un seul bit de stockage (plus un petit frais généraux pour la comptabilité - mais c'est généralement une constante, et sur l'ordre d'octets à des dizaines de octets au maximum).

Answer 5

Oui, vous pouvez utiliser un bitset .

Answer 6

Vous pourriez être intéressé à essayer la bibliothèque BITSCAN comme alternative. Récemment, une extension a été proposée pour la faible densité, que je ne suis pas sûr est votre cas, mais peut-être.

Answer 7

std :: bitset

Answer 8

Vous pouvez utiliser un tableau d'octets et un indice dans ce. Indice n serait l'indice d'octet n/8, bit # n%8. (En cas std :: bitset n'est pas disponible pour une raison quelconque).

Answer 9

Si N est connu au moment de la compilation, utilisez std :: bitset , sinon utilisez boost :: dynamic_bitset .

Answer 10

type A 'bool' ne sont pas stockées en utilisant uniquement 1 bit. De vos commentaires sur la taille, il semble utiliser 1 octet entier pour chaque bool.

A C comme façon de le faire serait:

uint8_t sieve[N/8]; //array of N/8 bytes

élément du tableau est la suivante:

result = sieve[index / 8] || (1 << (index % 8)); 

ou

result = sieve[index >> 3] || (1 << (index & 7));

1 fixé dans le tableau:

sieve[index >> 3] |= 1 << (index & 7);