Comment compter les zéros et les uns dans un fichier?

Question

Étant donné un fichier (binaire ou textuel), quel est le moyen le plus rapide ou le plus élégant en C++ de compter les uns et les zéros dans la représentation binaire de ce fichier?

Answer 1

Je vous recommande utiliser le tableau de résultats:

unsigned char cheating[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 
     4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 
     3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 
     5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 
     3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 
     5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 
     6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 
     4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 
     4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 
     7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 
     5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 
     6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; 

Après avoir lu le fichier en tant que tableau de caractères non signé, vous pouvez juste somme:

for (int i = 0; i < arraysize; i++) { 
     sum0+=8-cheating[unsignedbytearray[i]]; 
     sum1+=cheating[unsignedbytearray[i]]; 
    } 

Il est très difficile d'écrire du code , ce serait plus rapide ou plus élégant: P

Answer 2

Je lisais dans le fichier un unsigned int à la fois et comptais le nombre de bits activés dans chacun jusqu'à EOF. Vous pouvez utiliser l'algorithme de nombre clairsemé classique pour compter le nombre de 1 s dans une valeur unsigned int.

int bitcount (unsigned int n) 
{ 
    int count = 0 ; 
    while (n) { 
     count++ ; 
     n &= (n - 1) ; 
    } 
    return count ; 
} 

Il suffit de faire ce qui précède pour tous les lire unsigned int valeurs et garder un total de fonctionnement.

Answer 3

Sur la plupart des systèmes, le temps d'exécution principal sera lié aux e/S. Et comment atteindre les E/S les plus rapides dépend beaucoup du système. Il n'y a donc pas de réponse unique au "plus rapide".

Le plus "élégant" dépend des yeux qui voient. Donc, en résumé, aucune question n'a de réponse définitive; cela ressemble à pêcher des solutions à un devoir. Est-ce devoirs?

Answer 4

Créez un tableau de char de 256 longueurs. Flux à travers le fichier un octet à la fois en incrémentant la position du tableau de chaque octet. Hard code le nombre de 1 dans chacun des 256 octets dans un autre tableau. Multipliez les 2 tableaux et la somme.

Pas sûr de l'élégance et nécessite certainement plus de mémoire, mais pourrait être plus rapide que l'algorithme de linuxuser27.

Answer 5

Chaque fois que je veux savoir la meilleure astuce de manipulation de bits pour une tâche particulière, je commence ici: http://graphics.stanford.edu/~seander/bithacks.html

Sous la rubrique « Compter les bits mis en parallèle » ils énumèrent une méthode 12 de fonctionnement pour compter les bits situés dans un Entier 32 bits. Ils montrent également des méthodes pour les entiers supérieurs à 32 bits.

Answer 6

Je voudrais essayer d'utiliser std::bitset, il a une bonne mise en œuvre de la méthode count() (count interface) en conservant un tableau pré-calculé de longueur 256 pour le nombre de tous les octets possibles. Pour des zéros de comptage,

std::bitset<N> bs; 
size_t zero_count = bs.size() - bs.count(); 

J'initialiser file_zero_count = 0 et ouvrez le fichier. Ensuite, à chaque itération d'une boucle, je lisais N bits dans un bitset, et j'ajoute le zero_count de ces N bits au file_zero_count. Ensuite, lisez les N bits suivants et ainsi de suite ...

Le choix crucial est la valeur de N. Mon premier choix serait tel que N bits entrent dans une page de mémoire, par exemple. N = 4096.

Answer 7

Un moyen facile et rapide est de construire une table de consultation qui vous indique combien de caractères 1 a, par exemple. 'a' avec ASCII 97 a 3. Vous pouvez stocker une telle table de recherche dans un tableau de longueur fixe pour un accès constant. Chargez le fichier page par page dans la mémoire pour minimiser le nombre d'E/S et compter pour chaque char séquentiellement.

Si vous souhaitez plus d'informations sur le type de données que vous traitez, des solutions plus intéressantes peuvent être créées. Par exemple, si vous savez que le fichier contient des données textuelles en langage naturel, vous pouvez créer des tables de recherche pour des termes fréquents tels que «le», «de» et «et» pour accélérer les calculs de comptage. Une telle table de consultation peut être efficacement stockée dans une table de hachage.

Answer 8

je lirais dans l'octet par octet de fichier et compter le nombre de 1/0 dans chaque octet:

La raison pour laquelle je choisirais l'octet est qu'il est facile de mettre en place un LookupTable pour le nombre de 1 dans un octet à la main. Note: Je comptais le nombre de ceux dans un octet. Mais j'ai construit la table en arrière (donc c'est en fait un compte du nombre de 0 (car c'est l'inverse des 1)).

int countOne[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // Top Line + 1 2^5 (16 set) 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // Top Line + 1 2^6 (32 set) 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, // Top Line + 2 2^5 + 2^6 (16/32 set) 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // Top Line + 1 2^7 (64 set) 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, // Top Line + 2 2^5 + 2^7 (16/64 set) 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, // Top Line + 2 2^6 + 2^7 (32/64 set) 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, // Top Line + 3 2^5 + ^6 + 2^7 (16/32/64 set) 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // Top Line + 1 2^8 (128 set) 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, // Top Line + 2 2^5 + 2^8 (16/128 set) 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, // Top Line + 2 2^6 + 2^8 (32/128 set) 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, // Top Line + 3 2^5 + 2^6 + 2^8 (16/32/128 set) 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, // Top Line + 2 2^7 + 2^8 (64/128 set) 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, // Top Line + 3 2^5 + 2^7 + 2^8 (16/64/128 set) 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, // Top Line + 3 2^6 + 2^7 + 2^8 (32/64/128 set) 
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}; 

Maintenant, tout ce que vous devez faire est d'utiliser un std :: for_each qui iterater dans un cours d'eau (sans espaces en baisse. Maintenant, vous

counter = std::for_each(std::istreambuf_iterator<unsigned char>(file), 
         std::istreambuf_iterator<unsigned char>(), 
         couter); 

avez juste besoin de définir un type approprié pour le compteur et la

Answer 9

Voici un exemple complet (enfin, il y a un exercice pour l'implémenteur à la fin ...) Il utilise le nombre d'instructions 12 pour les 32 octets de http://graphics.stanford.edu/~seander/bithacks.html, et charge le fichier en utilisant mmap est (souvent) plus rapide que les autres lectures hods. Je pense que la seule chose à faire pour le rendre plus rapide serait de diviser le nombre entre plusieurs threads. Mais sur mon système, il traite déjà 10 Mo de fichiers en moins de 0,03s, ce qui me semble OK.

#include <fcntl.h> 
#include <sys/mman.h> 
#include <sys/stat.h> 
#include <iostream> 
#include <unistd.h> 

int main() 
{ 
    int fd = open("junk.txt",O_RDWR); 
    struct stat info; 
    fstat(fd, &info); 
    void * page = mmap(0, info.st_size, PROT_READ, MAP_PRIVATE, fd, 0); 
    uint64_t bitcount = 0; 
    //Lets ignore alignment issues for now - I think mmap guarantees that they're OK. 
    uint32_t * v_ptr = static_cast<uint32_t*>(page); 
    for(unsigned int i=0; i<info.st_size/4; ++i) 
    { 
    uint32_t v = *v_ptr; 
    v = v - ((v >> 1) & 0x55555555);     // reuse input as temporary 
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);  // temp 
    bitcount += ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count 
    ++v_ptr; 
    } 

    //Need to adjust for the last 0-3 bytes... Exercise for the reader 

    munmap(page, info.st_size); 

    std::cout<<"Total of "<<bitcount<<" set bits"<<std::endl; 
}