Jak liczyć zera i jedynek w pliku?

Question

Biorąc pod uwagę plik (binarny lub tekstowy), jaki jest najszybszy lub najbardziej elegancki sposób w C++ do zliczania zer i jedynek w binarnej reprezentacji tego pliku?

Answer 1

Polecam użyć wyników tablicy:

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

Po przeczytaniu pliku w jak unsigned char tablicy można po prostu suma:

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

Bardzo trudno jest napisać kod , który byłby szybszy lub bardziej elegancki: P

Answer 2

Przeczytałem w pliku jeden unsigned int na raz i policzyłem liczbę bitów włączonych w każdym do EOF. Możesz użyć klasycznego algorytmu zliczania rzadkiego, aby policzyć liczbę 1 s w wartości unsigned int.

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

Wystarczy wykonać powyższe wszystko czytać w unsigned int wartości i przechowywać łącznie biegu.

Answer 3

W większości systemów głównym czasem wykonania będzie granica i/o. A jak osiągnąć najszybsze i/o zależy w dużej mierze od systemu. Więc nie ma jednej odpowiedzi "najszybszej".

Najbardziej "elegancki" zależy od oczu, które widzą.

Podsumowując, żadne pytanie nie ma ostatecznej odpowiedzi; to brzmi jak łowienie rozwiązań dla zadania domowego. Czy to zadanie domowe?

Answer 4

Utwórz tablicę znaków o długości 256 znaków. Przesyłaj strumieniowo plik po bajcie w czasie zwiększając pozycję tablicy każdego bajtu. Twardy kod to liczba 1 w każdym z 256 bajtów w innej tablicy. Pomnóż 2 tablice i sumę.

Not sure about elegance i zdecydowanie wymaga więcej pamięci, ale może być szybszy niż algorytm linuxuser27.

Answer 5

Ilekroć chcę wiedzieć najlepszy kawałek manipulacji tricka dla konkretnego zadania, zacznę tutaj: http://graphics.stanford.edu/~seander/bithacks.html

Pod „Liczenie bity ustawione równolegle” oni listy metodę 12 operacji liczenia bity ustawione w sposób 32-bitowa liczba całkowita. Pokazują również metody dla liczb całkowitych większych niż 32-bitowe.

Answer 6

Chciałbym spróbować użyć std::bitset, ma dobrą implementację metoda count() () przez utrzymywanie wstępnie obliczonej tablicy o długości 256 dla zliczenia wszystkich możliwych bajtów . W celu zliczania zer:

Zainicjuję plik file_zero_count = 0 i otworzę plik. Następnie w każdej iteracji pętli czytałem bit N bitów i dodawałem zero_count bitów do file_zero_count. Następnie przeczytaj kolejne bity N itd.

Kluczowym wyborem jest wartość N. Mój pierwszy wybór byłby taki, że bity N pasowałyby do jednej strony pamięci, na przykład N = 4096.

Answer 7

Jednym z łatwych i szybkich sposobów jest zbudowanie tabeli przeglądowej, która wskaże liczbę 1 dowolnego z znaków, np. "a" z ASCII97 ma 3. Możesz przechowywać taką tablicę przeglądową w tablicy o stałej długości, aby uzyskać stały dostęp. Załaduj plik po stronie do pamięci, aby zminimalizować liczbę operacji we/wy i policzyć dla każdego znaku po kolei.

Jeśli masz więcej informacji o przetwarzanym typie danych, możesz utworzyć więcej ciekawych rozwiązań. Na przykład, jeśli wiesz, że plik zawiera dane tekstowe w języku naturalnym, możesz tworzyć tabele przeglądowe dla często występujących pojęć, takich jak ",", "of" i "oraz", aby przyspieszyć obliczenia liczenia. Taka tabela przeglądowa może być efektywnie przechowywana w tabeli mieszającej.

Answer 8

chciałbym przeczytać w pliku bajt po bajcie i policzyć 1/0 w każdym bajcie:

Powodem wybrałbym bajt jest to, że jest łatwy do ułożyła tablicowanie dla liczby 1 w bajcie ręcznie. Uwaga: Zliczałem liczbę w bajcie. Ale zbudowałem tabelę do tyłu (tak, że jest to właściwie liczba liczb 0 (ponieważ jest to odwrotność liczby 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}; 

Teraz wszystko co musisz zrobić, to użyć std :: for_each że iterater poprzek strumienia (bez spacji spada.

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

Teraz wystarczy określić odpowiedni typ na liczniku, a reszta jest historią:

Answer 9

Oto pełny przykład (no prawie jest to ćwiczenie dla implementora na końcu ...) Wykorzystuje on 12 instrukcji do 32-bajtowych wartości z http://graphics.stanford.edu/~seander/bithacks.html. Załaduje również plik używając mmap jako jest (często) szybszy niż inne przeczytane hods. Myślę, że jedyną rzeczą do zrobienia, aby przyspieszyć, byłoby podzielenie liczby na wiele wątków. Ale w moim systemie już przetwarza 10 MB plików poniżej 0,03, co wydaje mi się w porządku.

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