lavorazione enorme file di testo

Question

Problema: Ho un enorme file di testo grezzo (assumere dei 3gig), ho bisogno di passare attraverso ogni parola nel file e scoprire che una parola compare quante volte nel file .

La mia soluzione proposta: Dividere il file enorme in più file e ogni file diviso avrà le parole in un modo ordinato. Ad esempio, tutte le parole che iniziano con "a" verranno memorizzate in un file "_a.dic". Quindi, in qualsiasi momento non eseguiremo più di 26 file.

Il problema in questo approccio è,

posso utilizzare i flussi di leggere il file, ma ha voluto utilizzare i thread per leggere alcune parti del file. Ad esempio, leggi 0-1024 byte con un thread separato (almeno 4-8 thread basati sul numero di processori presenti nella casella). È possibile o sto sognando?

Qualche approccio migliore?

Nota: dovrebbe essere una soluzione basata su C++ o c pura. Nessun database ecc., Sono ammessi.

Answer 1

è necessario guardare a 'The Practice of Programming' da Kernighan e Pike, e in particolare il capitolo 3.

In C++, utilizzare una mappa basata sulle corde e un conteggio (std::map<string,size_t>, IIRC). Leggi il file (una volta - è troppo grande per leggerlo più di una volta), suddividendolo in parole man mano che vai (per una definizione di 'parola') e incrementando il conteggio nella voce della mappa per ogni parola che trovi.

In C, dovrai creare la mappa da solo. (Oppure trova "C Interfaces and Implementations" di David Hanson.)

Oppure puoi usare Perl, o Python, o Awk (che hanno tutti array associativi, equivalenti a una mappa).

Answer 2

soluzione basata su c?

Penso che perl sia nato per questo scopo preciso.

Answer 3

Non penso che l'utilizzo di più thread che leggono parti del file in parallelo possa aiutare molto. Mi aspetto che questa applicazione sia vincolata alla larghezza di banda e alla latenza del disco rigido, non al vero conteggio delle parole. Una tale versione multi-thread potrebbe effettivamente peggiorare perché l'accesso ai file "quasi-random" è in genere più lento dell'accesso "file lineare".

Nel caso in cui la CPU sia realmente occupata in una versione a thread singolo, potrebbe verificarsi una potenziale accelerazione. Un thread può leggere i dati in grandi blocchi e metterli in una coda di capacità limitata. Un mucchio di altri thread di lavoro potrebbero operare ciascuno sulla propria parte e contare le parole. Dopo aver completato i thread di lavoro del conteggio, è necessario unire i contatori di parole.

Answer 4

il flusso ha un solo cursore. Se accedi allo stream con più di un thread alla volta, non sarai sicuro di leggere dove vuoi. La lettura è fatta dalla posizione del cursore.

Quello che vorrei fare è avere un solo thread (forse quello principale) che legge lo stream e invia byte di lettura ad altri thread.

By esempio:

• #i Discussione è pronto e chiedere thread principale di dare parte successiva,
• thread principale di leggere il prossimo 1Mb e fornire loro di infilare 1,
• Discussione #i leggere il 1Mb e conta le parole che vuoi,
• Il thread # termina il suo lavoro e chiede ancora il prossimo 1Mb.

In questo modo è possibile separare la lettura del flusso all'analisi del flusso.

Answer 5

Quello che stai cercando è RegEx. Questo thread StackOverflow su C++ motori regex dovrebbe aiutare:

C++: what regex library should I use?

Answer 6

In primo luogo, sono abbastanza sicuro che il C/C++ non è il modo migliore per gestire questa situazione. Idealmente, dovresti usare anche qualche mappa/riduzione per il parallelismo.

Ma, assumendo i vostri limiti, ecco cosa farei.

1) Dividere il file di testo in blocchi più piccoli. Non devi farlo con la prima lettera della parola. Spaccialo in pezzi da 5000 parole. In pseudocodice, si farebbe qualcosa di simile:

index = 0

numwords = 0

mysplitfile = openfile (index-split.txt)

mentre (bigfile >> word)

mysplitfile << word 

numwords ++ 

if (numwords > 5000) 

    mysplitfile.close() 

    index++ 

    mysplitfile = openfile(index-split.txt) 

2) Utilizzare una struttura dati mappa condivisa e pthreads per deporre le uova nuove discussioni per leggere ciascuno dei sottofile. Anche in questo caso, pseudocodice:

maplock = create_pthread_lock()

sharedmap = std :: map()

per ogni file index-split.txt:

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

dump_map (sharedmap)

void myfunction (nome file, mappa condivisa) {

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) 

}

Ci scusiamo per la sintassi. Ultimamente sto scrivendo un sacco di pitone.

Answer 7

Mentre è possibile utilizzare un secondo thread per analizzare i dati dopo averli letti, probabilmente non si otterrà una quantità enorme. Provare a usare più di un thread per leggere i dati quasi certamente danneggerà la velocità piuttosto che migliorarla. L'utilizzo di più thread per elaborare i dati è inutile: l'elaborazione sarà molte volte più veloce della lettura, quindi anche con un solo thread aggiuntivo, il limite sarà la velocità del disco.

Un (possibile) modo per ottenere una velocità significativa è di bypassare i soliti iostreams - mentre alcuni sono quasi veloci quanto quelli di C FILE *, non so nulla di molto più veloce, e alcuni sono sostanzialmente Più lentamente. Se stai eseguendo questo su un sistema (ad esempio Windows) che ha un modello I/O che è notevolmente diverso da quello di C, puoi guadagnare molto di più con un po 'di attenzione.

Il problema è abbastanza semplice: il file che stai leggendo è (potenzialmente) più grande dello spazio cache che hai a disposizione - ma non otterrai nulla dalla cache, perché non rileggeresti blocchi di di nuovo il file (almeno se fai le cose in modo ragionevole). In quanto tale, si vuole dire al sistema di ignorare qualsiasi memorizzazione nella cache e trasferire semplicemente i dati il ​​più direttamente possibile dall'unità disco alla memoria in cui è possibile elaborarli. In un sistema simile a Unix, probabilmente è open() e read() (e non ti farà guadagnare molto). Su Windows, è CreateFile e ReadFile, passando il flag FILE_FLAG_NO_BUFFERING su CreateFile - e probabilmente raddoppierà la velocità se lo farai correttamente.

Hai anche ottenuto alcune risposte per sostenere l'elaborazione utilizzando vari costrutti paralleli. Penso che questi siano fondamentalmente sbagliati. A meno che tu non faccia qualcosa di orribilmente stupido, il tempo per contare le parole nel file sarà solo di pochi millisecondi più di quanto basta per leggere semplicemente il file.

La struttura che utilizzerei sarebbe avere due buffer, ad esempio un megabyte a testa. Leggi i dati in un buffer. Trasforma quel buffer nel tuo thread di conteggio per contare le parole in quel buffer. Mentre ciò accade, leggi i dati nel secondo buffer. Al termine, sostituisci i buffer e continua. C'è un po 'di elaborazione in più che devi fare nello scambiare i buffer per gestire una parola che può attraversare il confine da un buffer all'altro, ma è piuttosto banale (in pratica, se il buffer non finisce con il bianco spazio, sei ancora in una parola quando inizi a operare sul prossimo buffer di dati).

Finché si è sicuri che verrà utilizzato solo su una macchina multiprocessore (multi-core), l'utilizzo di thread reali va bene. Se esiste la possibilità che ciò avvenga su un computer single-core, è preferibile utilizzare un singolo thread con I/O sovrapposti.

Answer 8

Primo: decidere la struttura dati per il salvataggio delle parole.

La scelta ovvia è la mappa. Ma forse un Trie ti servirebbe meglio. In ogni nodo, si salva il conteggio per la parola. 0 significa che è solo una parte di una parola. È possibile inserire nel trie utilizzando un flusso e leggendo il carattere del file.

Secondo: multithreading si o no? Questo non è facile da rispondere. A seconda delle dimensioni, la struttura dei dati cresce e la modalità di parallelizzazione della risposta può essere diversa.

1. Singlethreaded - straitforward e facile da implementare.
2. Multithread con più thread di lettura e un datastructur. Quindi devi sincronizzare l'accesso al datastructure. In un Trie, è sufficiente bloccare il nodo in cui ci si trova effettivamente, in modo che più lettori possano accedere al datastructure senza troppe interferenze. Un albero autobilanciato potrebbe essere diverso, specialmente quando si riequilibra.
3. Multithreading con più thread di lettura, ciascuno con la propria infrastruttura. Ogni thread crea il proprio datastructure durante la lettura di una parte del file. Dopo che ognuno è finito, i risultati devono essere combinati (che dovrebbe essere facile).

Una cosa che devi pensare - si deve trovare un limite di parola per ogni thread per iniziare, ma che non dovrebbe rappresentare un grande problema (ad esempio, ogni thread passeggiate è iniziare fino a quando il primo confine di parola e inizia lì alla fine ogni thread finisce la parola su cui sta lavorando).

Answer 9

Come altri hanno indicato, il collo di bottiglia sarà l'I/O del disco. Pertanto suggerisco di utilizzare I/O sovrapposti. Questo in pratica inverte la logica del programma. Invece del tuo codice per determinare quando fare I/O, devi semplicemente dire al sistema operativo di chiamare il tuo codice ogni volta che ha terminato un po 'di I/O. Se si utilizza I/O completion ports, è anche possibile indicare al sistema operativo di utilizzare più thread per l'elaborazione dei blocchi di file.

Answer 10

Non C, e un po 'brutto, ma ci sono voluti 2 minuti per battere fuori:

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

loop su ciascuna linea con -n
Split ogni linea in @F parole con -a
Ogni $_ hash di parole hash %h
Una volta raggiunto lo END di file,
sort l'hash per la frequenza $h{$b}<=>$h{$a}
Se due frequenze sono identici, sorta in ordine alfabetico $a cmp $b
Stampa la frequenza $h{$w} e la parola $w
reindirizzare i risultati su file 'freq'

ho eseguito questo codice su un 3,3 File di testo GB con 580.000.000 di parole.
Perl 5.22 completato in 173 secondi.

mio file di input già aveva punteggiatura spogliato, e maiuscoli convertiti in minuscoli, utilizzare questo pezzo di codice:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(tempo di esecuzione di 144 secondi)

---

Lo script parola conteggio poteva alternativamente essere scritto in 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