Come faccio a contare gli zeri e quelli in un file?

Question

Dato un file (binario o testuale), qual è il modo più veloce o elegante in C++ per contare gli uni e gli zeri nella rappresentazione binaria di quel file?

Answer 1

mi sento di raccomandare di utilizzare i risultati di matrice:

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 }; 

Dopo aver letto il file come unsigned char serie si può semplicemente somma:

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

E 'molto difficile da scrivere codice , che sarebbe più veloce o più elegante: P

Answer 2

Vorrei leggere nel file uno unsigned int alla volta e contare il numero di bit attivati ​​in ciascuno fino a EOF. È possibile utilizzare l'algoritmo di calcolo sparse classico per contare il numero di 1 s in un valore unsigned int.

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

solo fare il sopra per tutti letto in unsigned int valori e mantenere un totale parziale.

Answer 3

Sulla maggior parte dei sistemi il tempo di esecuzione principale sarà i/o-bound. E come ottenere l'I/O più veloce dipende molto dal sistema. Quindi non c'è una sola risposta al "più veloce".

La maggior parte "elegante" dipende dagli occhi che vedono.

Quindi, in sintesi, nessuna delle due domande ha una risposta definitiva; suona come la pesca di soluzioni per un compito a casa. Sono i compiti?

Answer 4

Creare un array di caratteri di lunghezza 256. Flusso attraverso il file un byte alla volta incrementando la posizione dell'array di ogni byte. Codice hard il numero di 1s in ciascuno dei 256 byte in un altro array. Moltiplica i 2 array e somma.

Non sono sicuro dell'eleganza e richiede sicuramente più memoria, ma potrebbe essere più veloce dell'algoritmo di linuxuser27.

Answer 5

Ogni volta che voglio sapere il miglior trick manipolazione po 'per un particolare compito, mi metto qui: http://graphics.stanford.edu/~seander/bithacks.html

In "Counting bit impostati, in parallelo" elencano un metodo 12 operazione per contare i bit impostati in un Numero intero a 32 bit. Mostrano anche metodi per numeri interi maggiori di 32 bit.

Answer 6

Proverei ad usare std::bitset, ha una buona implementazione di il metodo count() (count interface) mantenendo una matrice pre-calcolata di lunghezza 256 per il conteggio di tutti i possibili byte . Per zeri conteggio,

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

avrei inizializzare file_zero_count = 0 e aprire il file. Quindi, in ogni iterazione di un ciclo, leggevo i bit N in un set di bit e aggiungo lo zero_count di quei bit N allo file_zero_count. Quindi leggi i successivi N bit e così via ...

La scelta cruciale è il valore di N. La mia prima scelta sarebbe tale che i bit N si inseriscano in una pagina di memoria, ad es. N = 4096.

Answer 7

Un modo facile e veloce consiste nel creare una tabella di ricerca che indichi quanti caratteri 1 hanno, ad es. 'a' con ASCII 97 ha 3. È possibile memorizzare una tale tabella di ricerca in una matrice a lunghezza fissa per l'accesso a tempo costante. Caricare il file pagina per pagina nella memoria per ridurre al minimo il numero di I/O e contare per ogni carattere in sequenza.

Se si dispone di ulteriori informazioni sul tipo di dati che si stanno elaborando, è possibile creare soluzioni più interessanti. Ad esempio, se si sa che il file contiene dati testuali in linguaggio naturale, è possibile creare tabelle di ricerca per termini ricorrenti come "il", "di" e "e" per accelerare i calcoli di conteggio. Tale tabella di ricerca può essere memorizzata in modo efficiente nella tabella hash.

Answer 8

avrei letto nel file byte per byte e contare il numero di 1/0 in ogni byte:

Il motivo avrei scelto byte è che è facile mettere insieme un LOOKUPTABLE per il numero di 1 in un byte a mano. Nota: stavo contando il numero di quelli in un byte. Ma ho costruito la tabella all'indietro (quindi è in realtà un conteggio del numero di 0 (poiché è l'inverso degli 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}; 

Ora tutto quello che dovete fare è utilizzare uno std :: for_each che iterater attraverso un flusso (senza spazi cadere.

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

Ora non vi resta che definire un tipo appropriato per il contatore e la il resto è storia

Answer 9

Ecco un esempio completo (beh quasi c'è un esercizio per l'implementatore alla fine ...) Utilizza il conteggio di 12 istruzioni per i valori a 32 byte da http://graphics.stanford.edu/~seander/bithacks.html. Inoltre carica il file utilizzando mmap come quello è (spesso) più veloce di altri read read hods. Penso che l'unica cosa da fare per renderlo più veloce sarebbe dividere il conteggio su più thread. Ma sul mio sistema già processa file da 10 MB in meno di 0.03, il che mi sembra 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; 
}