¿Cómo cuento los ceros y unos en un archivo?

Question

Dado un archivo (binario o textual), ¿cuál es la forma más rápida o más elegante en C++ para contar los unos y ceros en la representación binaria de ese archivo?

Answer 1

le recomiendo que utilice los resultados de matriz:

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

Después de leer el archivo en tan sin firma matriz de caracteres puede simplemente suma:

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

Es muy difícil escribir código , eso sería más rápido o más elegante: P

Answer 2

Leería en el archivo un unsigned int a la vez y contaría el número de bits activados en cada uno hasta EOF. Puede usar el algoritmo de conteo disperso clásico para contar el número de 1 en un valor de unsigned int.

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

Eso sí, lo anterior para todos leído en unsigned int valores y llevando una cuenta continua.

Answer 3

En la mayoría de los sistemas, el tiempo de ejecución principal estará limitado por la conexión de E/S. Y cómo lograr la mayor velocidad de E/S depende en gran medida del sistema. Entonces, no hay una sola respuesta para "más rápido".

La mayoría de los "elegantes" depende de los ojos que ven.

Así que, en resumen, ninguna de las dos preguntas tiene una respuesta definitiva; suena como buscar soluciones para una tarea asignada. ¿Es tarea?

Answer 4

Crea una matriz de caracteres de 256 longitudes. Transmita por el archivo un byte a la vez incrementando la posición de la matriz de cada byte. Código duro el número de 1s en cada uno de los 256 bytes en otra matriz. Multiplica las 2 matrices y suma.

No estoy seguro acerca de la elegancia y definitivamente requiere más memoria, pero podría ser más rápido que el algoritmo de linuxuser27.

Answer 5

Siempre que quiero saber el mejor truco de manipulación de bits para una tarea en particular, comienzo aquí: http://graphics.stanford.edu/~seander/bithacks.html

En "Contando bits puestos, de forma paralela" que lista un método de funcionamiento 12 para contar los bits puestos en una Entero de 32 bits. También muestran métodos para enteros mayores a 32 bits.

Answer 6

Yo trataría de usar std::bitset, tiene una buena implementación de el método count() (count interface) manteniendo una matriz calculada previamente de longitud 256 para el recuento de todos los bytes posibles. Para ceros conteo,

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

Me inicializar file_zero_count = 0 y abrir el archivo. Luego, en cada iteración de un ciclo, leería N bits en un conjunto de bits, y agregaría el zero_count de esos N bits al file_zero_count. A continuación, lea los siguientes bits N y así sucesivamente ...

La opción crucial es el valor de N. Mi primera opción sería tal que N bits encajen en una página de memoria, por ej. N = 4096.

Answer 7

Una forma fácil y rápida es crear una tabla de búsqueda que indique cuántos 1 tiene alguno de los caracteres, p. Ej. 'a' con ASCII 97 tiene 3. Puede almacenar dicha tabla de búsqueda en una matriz de longitud fija para acceso de tiempo constante. Cargue el archivo página por página en la memoria para minimizar el número de E/S y contar para cada carácter secuencialmente.

Si obtiene más información sobre el tipo de datos que está procesando, se pueden crear soluciones más interesantes. Por ejemplo, si sabe que el archivo contiene datos textuales en lenguaje natural, puede crear tablas de búsqueda para términos frecuentes como 'el', 'de' y 'y' para acelerar los cálculos de conteo. Dicha tabla de búsqueda se puede almacenar eficientemente en tabla hash.

Answer 8

me gustaría leer en el archivo de byte a byte y contar el número de 1/0 en cada byte:

La razón por la que elegiría byte es que es fácil de armar un LookupTable para el número de 1 en un byte a mano. Nota: estaba contando el número de unidades en un byte. Pero construí la tabla al revés (por lo que en realidad es un recuento del número de 0 (ya que es el inverso de los 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}; 

Ahora todo lo que necesita hacer es utilizar un std :: for_each que iterater través de una corriente (sin espacios cayendo.

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

Ahora sólo tiene que definir un tipo apropiado para el contador y el el resto es historia.

Answer 9

He aquí un ejemplo completo (bueno, casi hay un ejercicio para el implementador al final ...) Utiliza el conteo de 12 instrucciones para valores de 32 bytes de http://graphics.stanford.edu/~seander/bithacks.html. También carga el archivo usando mmap como ese es (a menudo) más rápido que otras leídas hods. Creo que lo único que hay que hacer para hacerlo más rápido sería dividir el recuento en varios hilos. Pero en mi sistema ya procesa archivos de 10MB en menos de 0.03s, lo cual me parece bien.

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