Tableau de bits en C++

Lorsque vous travaillez avec un Projet d'Euler problèmes, j'ai souvent besoin de gros (> 10**7) tableau de bits.

Mon approche normale est l'une des:

bool* sieve = new bool[N];

bool sieve[N];

Lorsque N = 1 000 000 de mon programme utilise 1 méga-octet (8 * 1 000 000 bits).

Est-il un moyen plus efficace pour utiliser, stocker peu de tableaux de bool en c++?

- je mettre en œuvre tamis de l'algorithme à l'aide de vecteurs.. il peut tenir que de nombreux numéros.
Double Possible de C/C++ efficace tableau de bits

OriginalL'auteur King Vash | 2010-09-27

20

Utilisation std::bitset (si N est une constante), sinon utiliser std::vector<bool> comme d'autres l'ont mentionné (mais n'oubliez pas de lire cet excellent article par Herb Sutter)

Un bitset est un conteneur spécial de la classe 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 qu'un peu (ce qui est huit fois moins que le plus petit type élémentaire en C++: char).

MODIFIER:

Herb Sutter (dans cet article) mentionne que

La raison std::vector< bool > est pas conforme, c'est qu'il tire des trucs sous les couvertures dans une tentative pour optimiser l'espace: au Lieu de stocker une char ou int pour chaque bool[1] (prendre au moins 8 fois l'espace, sur les plates-formes avec 8 bits de caractères), il emballe les booléens et les magasins comme des bits individuels(à l'intérieur, disons, de caractères) dans sa représentation interne.

std::vector < bool > forces une optimisation spécifique à tous les utilisateurs par sa consécration dans la norme. Ce n'est pas une bonne idée; les différents utilisateurs ont des besoins différents, et maintenant tous les utilisateurs de vecteur doit payer la pénalité de performances, même si elles ne veulent pas ou ont besoin de la réduction de l'espace.

EDIT 2:

Et si vous avez utilisé le coup de pouce que vous pouvez utiliser boost::dynamic_bitset(si N est connu au moment de l'exécution)

OriginalL'auteur Prasoon Saurav
12

Pour le meilleur ou pour le pire, std::vector<bool> utilisation de bits au lieu de bool, pour économiser de l'espace. Utilisez donc std::vector comme vous doit avoir été en premier lieu.

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

OriginalL'auteur GManNickG
4

Un 'bool' type n'est pas stocké à l'aide de seulement 1 bit. À partir de votre commentaire à propos de la taille, il semble qu'il utilise 1 octet entier pour chaque bool.

Un C comme façon de faire, ce serait:
```
uint8_t sieve[N/8]; //array of N/8 bytes
```
et puis logique OU d'octets 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 des octets.

upvoted, bonne idée, peut-être, il est N/8+1, c'est peu emballé tableau.

OriginalL'auteur whooops
4

Vous pourriez chercher std::bitset et std::vector<bool>. Ce dernier est souvent recommandé contre, parce que, malgré les vector dans le nom, il n'a pas vraiment d'agir comme un vecteur de tout autre type d'objet, et, en fait, ne répond pas aux exigences d'un conteneur en général. Néanmoins, il peut être assez utile.

Otoh, que, rien ne va (au moins de façon fiable) magasin 1 million de bool valeurs en moins de 1 million de bits. Il ne peut simplement pas être fait avec certitude. Si vos ensembles de bits contiennent un certain degré de redondance, il existe différents schémas de compression qui peut être efficace (par exemple, LZ*, Huffman, arithmétique), mais sans en connaître le contenu, il est impossible de dire qu'ils seraient pour certains. L'une de ces solutions, cependant, normalement stocker chaque bool/bits dans un seul bit de stockage (plus un peu généraux de la comptabilité, mais c'est généralement une constante, et sur l'ordre des octets des dizaines d'octets au plus).

OriginalL'auteur Jerry Coffin
2

Oui, vous pouvez utiliser un bitset.

Alors que ce lien peut répondre à la question, il est préférable d'inclure les parties essentielles de la réponse et de fournir le lien de référence. Lien-ne répond peut devenir non valide si la page liée changements.

OriginalL'auteur Niki Yoshiuchi
2

Vous pourriez être intéressé à essayer de le BITSCAN bibliothèque comme une alternative. Récemment, une extension a été proposée pour le caractère, je ne suis pas sûr, c'est votre cas, mais il pourrait être.

OriginalL'auteur chesslover
0

Essayer std::bitset

OriginalL'auteur Dima
0

Vous pouvez utiliser un tableau d'octets et de l'index. L'indice de n serait en octets de l'indice de n/8, bit # n%8. (Dans le cas std::bitset n'est pas disponible pour une raison quelconque).

OriginalL'auteur driis
0

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

OriginalL'auteur Eugen Constantin Dinca
0

Un 'bool' type n'est pas stocké à l'aide de seulement 1 bit. À partir de votre commentaire à propos de la taille, il semble qu'il utilise 1 octet entier pour chaque bool.

Un C comme façon de faire, ce serait:
```
uint8_t sieve[N/8]; //array of N/8 bytes
```
élément du tableau est:
```
result = sieve[index / 8] || (1 << (index % 8)); 
```
ou
```
result = sieve[index >> 3] || (1 << (index & 7));
```
set 1 dans la gamme:
```
sieve[index >> 3] |= 1 << (index & 7);
```
OriginalL'auteur Vladimir

Vous devez vous connecter pour publier un commentaire.