tworzenie ogromny pliki tekstowe

Question

Problem: Mam ogromny plik tekstowy surowy (zakładamy z 3gig), muszę przejść przez każdego słowa w pliku i dowiedzieć się, że to słowo pojawia się ile razy w pliku .

My Proponowane rozwiązanie: Splitu ogromny plik na wiele plików i każdy podzielony plików będą miały słowa w sortowanych sposób. Na przykład: wszystkie słowa rozpoczynające się od "a" będą przechowywane w pliku "_a.dic". Tak więc w dowolnym momencie nie wykonamy więcej niż 26 plików.

Problem w tym podejściu jest

mogę używać strumieni do odczytu pliku, ale chciał użyć wątki czytać niektóre części pliku. Na przykład odczytaj 0-1024 bajtów z osobnym wątkiem (co najmniej 4-8 wątków w oparciu o liczbę procesorów w pudełku). Czy to jest możliwe, czy też śnię?

Lepsze podejście?

Uwaga: Powinno to być rozwiązanie oparte na czystym C++ lub c. Żadne bazy danych itp. Nie są dozwolone.

Answer 1

Trzeba spojrzeć na '' The Practice of Programming przez Kernighana i Pike, a konkretnie Rozdział 3.

w C++, korzystać z mapy w oparciu o ciągi i liczenia (std::map<string,size_t>, IIRC). Przeczytaj ten plik (raz - jest za duży, aby przeczytać więcej niż jeden raz), dzieląc go na słowa w miarę twoich słów (dla jakiejś definicji słowa "słowo") i zwiększając liczbę w pozycji mapy dla każdego znalezionego słowa.

W języku C konieczne będzie samodzielne utworzenie mapy. (Albo znajdź "Hansa-Davida Hansona" ".)

Możesz też użyć Perla, Pythona lub Awk (wszystkie mają tablice asocjacyjne, równoważne mapie).

Answer 2

c oparte rozwiązanie?

Myślę, że perl narodził się właśnie w tym celu.

Answer 3

Nie sądzę, że używanie wielu wątków, które czytają części pliku równolegle, znacznie pomoże. Spodziewam się, że ta aplikacja jest związana z przepustowością i opóźnieniem dysku twardego, a nie z faktycznym liczeniem słów. Taka wersja wielowątkowa może faktycznie działać gorzej, ponieważ "quasi-losowy" dostęp do plików jest zwykle wolniejszy niż dostęp do "pliku liniowego".

W przypadku, gdy procesor jest bardzo zajęty w wersji jednowątkowej, może dojść do potencjalnej przyspieszenia. Jeden wątek mógł odczytać dane w dużych porcjach i umieścić je w kolejce o ograniczonej pojemności. Pęczek innych wątków roboczych może obsługiwać każdy na własnej porcji i liczyć słowa. Po zakończeniu wątków robota zliczającego musisz scalić liczniki słów.

Answer 4

strumień ma tylko jeden kursor. Jeśli uzyskasz dostęp do strumienia z więcej niż jednym wątkiem naraz, nie będziesz mieć pewności, że czytasz tam, gdzie chcesz. Odczytywanie odbywa się z pozycji kursora.

Co mogę zrobić, to mieć tylko jeden wątek (może główny), który odczytuje strumień i wysyła bajty odczytu do innych wątków.

Poprzez przykład:

• #I wątek jest gotowy i poprosić głównego wątku, aby nadać mu następną część,
• Główny wątek przeczytać następny 1Mb i dostarczyć je do gwintu 1,
• Temat #I czytać 1Mb i policz słowa, jak chcesz,
• Wątek #i kończy swoją pracę i pytaj ponownie o następną 1Mb.

W ten sposób można oddzielić odczytywanie strumienia do analizy strumienia.

Answer 5

Czego szukasz to RegEx. Wątek Stackoverflow na C++ regex silniki powinny pomóc:

C++: what regex library should I use?

Answer 6

Po pierwsze, jestem pewien, że C/C++ nie jest to najlepszy sposób, aby sobie z tym poradzić. Idealnie byłoby użyć trochę mapy/zmniejszyć dla równoległości.

Ale zakładając swoje ograniczenia, oto, co zrobię.

1) Podziel plik tekstowy na mniejsze części. Nie musisz tego robić przez pierwszą literę słowa. Po prostu podziel je na, powiedzmy, 5000 słów. W Pseudokod, chcesz zrobić coś takiego:

index = 0

NUMWORDS = 0

mysplitfile = openFile (indeks-split.txt)

while (bigfile >> słowo)

mysplitfile << word 

numwords ++ 

if (numwords > 5000) 

    mysplitfile.close() 

    index++ 

    mysplitfile = openfile(index-split.txt) 

2) Użyj wspólnej struktury danych mapy i pthreads, aby odradzać nowe wątki, aby odczytać każdy z podtekstów. Ponownie, pseudokod:

maplock = create_pthread_lock()

sharedmap = std :: map()

dla każdego pliku indeksu-split.txt:

spawn-new-thread(myfunction, filename, sharedmap, lock) 

dump_map (sharedmap)

void myfunction (filename, sharedmap) {

localmap = std::map<string, size_t>(); 

file = openfile(filename) 

while (file >> word) 

    if !localmap.contains(word) 
     localmap[word] = 0 

    localmap[word]++ 

acquire(lock) 
for key,value in localmap 
    if !sharedmap.contains(key) 
     sharedmap[key] = 0 

    sharedmap[key] += value 
release(lock) 

}

Przepraszamy za składnię. Ostatnio pisałem dużo Pythona.

Answer 7

Mimo że możesz użyć drugiego wątku do analizy danych po ich przeczytaniu, prawdopodobnie nie uzyskasz w ten sposób ogromnej ilości danych. Próba użycia więcej niż jednego wątku do odczytania danych prawie na pewno wpłynie na szybkość, a nie na jego poprawę. Używanie wielu wątków do przetwarzania danych nie ma sensu - przetwarzanie będzie wiele razy szybsze niż czytanie, więc nawet z jednym dodatkowym wątkiem, limitem będzie prędkość dysku.

Jednym (możliwym) sposobem na uzyskanie znacznej prędkości jest ominięcie zwykłych iostreamów - podczas gdy niektóre są prawie tak szybkie, jak przy użyciu C FILE *, nic nie wiem o wiele szybciej, a niektóre są znacznie wolniej. Jeśli używasz tego w systemie (np. Windows), który ma model I/O, który wyraźnie różni się od C, możesz uzyskać znacznie więcej przy odrobinie staranności.

Problem jest dość prosty: plik, który czytasz jest (potencjalnie) większy niż przestrzeń pamięci podręcznej, którą masz dostęp - ale nic nie zyskasz dzięki buforowaniu, ponieważ nie będziesz ponownie czytać fragmentów plik ponownie (przynajmniej jeśli robisz to rozsądnie). W związku z tym chcesz powiedzieć systemowi, aby pominął buforowanie i po prostu przesyłaj dane tak bezpośrednio, jak to możliwe, z dysku twardego do pamięci, gdzie możesz je przetworzyć. W systemie uniksopodobnym, to prawdopodobnie open() i read() (i nie przyniesie Ci to dużo). W systemie Windows to CreateFile i ReadFile, przekazując flagę FILE_FLAG_NO_BUFFERING do CreateFile - i prawdopodobnie zwiększy się dwukrotnie twoja prędkość, jeśli zrobisz to dobrze.

Dostałeś również kilka odpowiedzi zalecających przetwarzanie przy użyciu różnych konstrukcji równoległych. Myślę, że są one zasadniczo błędne. O ile nie zrobisz czegoś okropnie głupiego, czas policzenia słów w pliku będzie o kilka milisekund dłuższy niż po prostu odczytanie pliku.

Strukturę, której użyłbym, miałaby dwa bufory, powiedzmy, po jednym megabajcie. Odczytaj dane do jednego bufora. Odwróć ten bufor do wątku zliczającego, aby policzyć słowa w tym buforze. W tym czasie odczytaj dane do drugiego bufora. Gdy już to zrobisz, po prostu zamień bufory i kontynuuj. Jest trochę dodatkowego przetwarzania, które musisz wykonać, wymieniając bufory, aby poradzić sobie ze słowem, które może przekroczyć granicę z jednego bufora do drugiego, ale jest to dość trywialne (w zasadzie, jeśli bufor nie kończy się na kolorze białym spacja, wciąż jesteś słowem, gdy zaczniesz operować na następnym buforze danych).

Dopóki jesteś pewny, że będzie używany tylko na maszynie wieloprocesorowej (wielordzeniowej), używanie prawdziwych wątków jest w porządku. Jeśli jest szansa, że ​​kiedykolwiek zostanie to zrobione na maszynie jednordzeniowej, lepiej od razu użyć jednego wątku z nakładającymi się we/wy.

Answer 8

Najpierw - wybierz strukturę danych do zapisywania słów.

Oczywistym wyborem jest mapa. Ale może Trie będzie Ci lepiej służyć. W każdym węźle zapisujesz liczbę słów. 0 oznacza, że ​​jest to tylko część słowa. Możesz wstawić do triesu za pomocą strumienia i odczytać charakterystykę pliku.

Po drugie - wielowątkowość tak lub nie? Nie jest łatwo odpowiedzieć na to pytanie. W zależności od rozmiaru struktura danych rośnie, a także sposób równoległości odpowiedzi mogą się różnić.

1. Singlethreaded - straitforward i łatwe do wykonania.
2. Wielowątkowe z wieloma wątkami czytnika i jednym datastructurem. Następnie musisz zsynchronizować dostęp do bazy danych. W Trie wystarczy zablokować węzeł, w którym aktualnie się znajdujesz, aby wielu czytelników mogło uzyskać dostęp do bazy danych bez większych zakłóceń. Samo-równoważące drzewo może być inne, zwłaszcza przy równoważeniu.
3. Wielowątkowe z wątkami wielu czytników, każdy z własną strukturą danych. Każdy wątek buduje własną strukturę danych podczas odczytywania części pliku. Po zakończeniu każdego z nich wyniki muszą zostać połączone (co powinno być łatwe).

Jedną z rzeczy, o której musisz pomyśleć - musisz znaleźć granicę słów dla każdego wątku, aby rozpocząć, ale to nie powinno stanowić wielkiego problemu (np. Każdy wątek idzie, dopóki nie pojawi się pierwsza granica słowa i zaczyna się tam na końcu każdy wątek kończy słowo, nad którym pracuje).

Answer 9

Jak wskazali inni, wąskim gardłem będzie dysk I/O. W związku z tym sugeruję stosowanie nakładających się operacji we/wy. To zasadniczo odwraca logikę programu. Zamiast swojego kodu wiążącego się z określeniem, kiedy wykonać operacje wejścia/wyjścia, po prostu mów systemowi operacyjnemu, aby zadzwonił do twojego kodu, gdy tylko skończy trochę operacji we/wy. Jeśli używasz I/O completion ports, możesz nawet powiedzieć systemowi operacyjnemu, aby używał wielu wątków do przetwarzania porcji plików.

Answer 10

Nie C i nieco brzydki, ale zajęło tylko 2 minuty walić się:

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

pętli nad każdym wierszu z -n
Splitu każdą linię do @F słów z -a
Each $_ przyrost znaków hash %h
Po osiągnięciu END z file,
sort hash przez częstotliwość $h{$b}<=>$h{$a}
Jeśli dwie częstotliwości są identyczne, sortować alfabetycznie $a cmp $b
Drukuj częstotliwość $h{$w} a słowo $w
przekierować wyniki do pliku „freq”

Pobiegłem ten kod na 3.3 Plik tekstowy GB z 580 000 000 słów.
Perl 5.22 ukończono za 173 sekundy.

Mój plik wejściowy już interpunkcyjny odpędza się, a wielka konwertowane na małe litery, używając ten kawałek kodu:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(runtime 144 sekund)

---

Skrypt słowo liczenia mógł na przemian napisać w awk:
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq