Verarbeitung von großen Textdateien

StackOverflow https://stackoverflow.com/questions/1625299

  •  06-07-2019
  •  | 
  •  

Frage

Problem: Ich habe eine riesige rohe Textdatei (unter der Annahme von 3Gig), muß ich in der Datei durch jedes Wort gehen und finden Sie heraus, dass ein Wort erscheint, wie oft in der Datei.

Mein Lösungsvorschlag: Teilen Sie die große Datei in mehrere Dateien und jede geteilte Datei wird also in einer sortierten Weise haben. Zum Beispiel, Alle Wörter, die mit " a " wird in einem " _a.dic " Datei gespeichert werden. Also, zu jeder Zeit, dass wir nicht mehr als 26 Dateien execeed.

Das Problem bei diesem Ansatz ist,

kann ich Streams verwenden, um die Datei zu lesen, aber ich wollte Threads verwenden, um bestimmte Teile der Datei zu lesen. Zum Beispiel las 0-1024 Bytes mit einem separaten Faden (atleast hat 4-8 Fäden auf der Basis der Nr. Von Prozessoren in dem Feld vorhanden ist). Ist dies möglich ist, oder träume ich?

Gibt es eine besseren Ansatz?

Hinweis: Es sollte eine reine C ++ oder C-basierte Lösung sein. Keine Datenbanken usw., sind nicht erlaubt.

War es hilfreich?

Lösung

Sie müssen von Kernighan auf ' The Practice of Programming ' aussehen und Pike und insbesondere Kapitel 3.

In C ++ verwenden, um eine Karte basierend auf den Saiten und eine Zählung (std::map<string,size_t>, IIRC). Lesen Sie die Datei (einmal - es ist zu groß mehr als einmal zu lesen), es in Worte zu fassen Spaltung, wie Sie gehen (für einige Definition von ‚Wort‘), und Erhöhen der Zählung in der Karte Eintrag für jedes Wort, das Sie finden

In C, werden Sie die Karte selbst erstellen müssen. (Oder finden David Hanson " C Schnittstellen und Realisierungen ").

Oder Sie verwenden Perl oder Python oder Awk (von denen alle assoziative Arrays haben, das entspricht einer Karte).

Andere Tipps

Ich glaube nicht, mehrere Threads verwenden, die Teile der Datei parallel gelesen wird viel helfen. Ich würde erwarten, dass diese Anwendung auf die Bandbreite und Latenzzeit von Ihrer Festplatte gebunden ist, nicht das eigentliche Wort Zählen. Eine solche Multi-Threaded-Version könnte tatsächlich schlechter abschneiden, weil „quasi-random“ Dateizugriff typischerweise langsamer als „lineare Datei“ Zugriff ist.

Falls die CPU wirklich beschäftigt in einer Singlethread-Version könnte es eine mögliche Geschwindigkeit betragen. Ein Thread konnte die Daten in großen Brocken lesen und sie in eine Schlange von begrenzten Kapazität gesetzt. Ein Bündel von anderen Worker-Threads könnten jeweils auf eigene Brocken betreiben und die Worte zählen. Nach der Zählung Worker-Threads beendet, um die Wortzähler zu fusionieren haben.

Erste - entscheiden über die Datenstruktur für die Worte sparen.

Die offensichtliche Wahl ist die Karte. Aber vielleicht ein Trie würden Sie besser dienen. In jedem Knoten, speichern Sie die Zählung für das Wort. 0 bedeutet, dass sie nur einen Teil eines Wortes ist. Sie können in den Trie einfügen einen Stream und lesen Sie Ihre Datei zeichenorientierte.

Second - Multithreading ja oder nein? Dieser ist nicht leicht zu beantworten. Je nach Größe der Datenstruktur wächst und wie Sie parallelisieren die Antwort unterschiedlich sein.

  1. Singlethreaded -. Straitforward und einfach zu implementieren
  2. Multithreaded mit mehreren Leser-Threads und ein datastructur. Dann haben Sie den Zugriff auf die Datenstruktur zu synchronisieren. In einem Trie, müssen Sie nur den Knoten, den Sie tatsächlich in sperren, so dass mehrere Leser die Datenstruktur ohne viel Einmischung zugreifen können. Ein Selbst-Balancing Baum könnte anders sein, vor allem, wenn Rebalancing.
  3. Multithreaded mit mehreren Leser-Threads, die jeweils mit ihrer eigenen Datenstruktur. Jeder Thread baut es eigene Datenstruktur ist, während ein Teil der Datei zu lesen. Nachdem jeder fertig ist, haben die Ergebnisse kombiniert werden (was einfach sein sollte).

Eine Sache, die Sie haben zu denken - Sie haben für jeden Thread eine Wortgrenze zu finden, zu beginnen, aber das sollte ein großes Problem nicht darstellen (zB jeden Thread geht es bis zur ersten Wortgrenze zu beginnen hat und beginnt dort, an dem Ende jeder Thread beendet das Wort es funktioniert auf).

Während Sie einen zweiten Thread verwenden können, um die Daten nach dem Lesen sie zu analysieren, sind Sie wahrscheinlich gehen zu gewinnen nicht eine riesige Menge von so tun. Der Versuch, mehr als ein Thread zu verwenden, um die Daten zu lesen Geschwindigkeit mit ziemlicher Sicherheit schaden, anstatt sie zu verbessern. mehrere Threads unter Verwendung der Daten zu verarbeiten, ist sinnlos -. Verarbeitung oft schneller als das Lesen sein wird, so dass auch mit nur einem zusätzlichen Faden, die Grenze der Plattengeschwindigkeit sein wird

Eine (mögliche) Art und Weise erhebliche Geschwindigkeit zu gewinnen ist es, die üblichen iostreams zu umgehen - während einige fast so schnell wie mit C FILE * 's, ich weiß nicht, von allem, was wirklich schneller ist, und einige sind wesentlich langsamer . Wenn Sie diese auf einem System ausgeführt wird (zum Beispiel Windows), die ein I / O-Modell hat, die von C sind deutlich anders ist, können Sie wesentlich mehr mit einer wenig Sorgfalt gewinnen.

Das Problem ist ziemlich einfach: Die Datei, die Sie gerade lesen ist (möglicherweise) größer ist als der Cache-Speicherplatz Sie zur Verfügung haben - aber Sie werden nichts von Caching gewinnen, weil Sie nicht Brocken das geht noch einmal zu lesen Datei wieder (zumindest wenn man die Dinge vernünftig tun). Als solche wollen Sie das System sagen, jede Caching zu umgehen, und nur Daten zu übertragen, so direkt wie möglich aus dem Laufwerk zu Ihrem Speicher, wo Sie es verarbeiten können. In einem Unix-ähnlichen System, das ist wahrscheinlich open() und read() (und werden Sie nicht viel gewinnen). Unter Windows ist die CreateFile und ReadFile, die FILE_FLAG_NO_BUFFERING Flagge CreateFile vorbei - und es wird wahrscheinlich die Geschwindigkeit in etwa verdoppeln, wenn Sie es richtig machen

.

Sie haben auch ein paar Antworten bekommen dabei die Verarbeitung unter Verwendung von verschiedenen parallelen Konstrukte befürworten. Ich denke, diese grundlegend falsch sind. Es sei denn, Sie etwas schrecklich dumm tun, wird die Zeit, die Worte in der Datei zu zählen nur wenige Millisekunden länger, als es nimmt einfach die Datei zu lesen.

Die Struktur wäre ich verwenden würde, zwei Puffer haben, sagen wir, ein Megabyte pro Stück. Lesen von Daten in einem Puffer. Drehen Sie, dass über Ihre Zählen Thread puffern die Worte in diesem Puffer zu zählen. Während das passiert, lesen Daten in den zweiten Puffer. Wenn diese fertig sind, tauschen grundsätzlich Puffer und fortzusetzen. Es gibt ein wenig zusätzliche Verarbeitung Sie Puffer in Swapping tun müssen, werden mit einem Wort zu befassen, die die Grenze von einem Puffer zum nächsten durchqueren können, aber es ist ziemlich trivial (im Grunde, wenn der Puffer mit weißem endet nicht Raum, du ist immer noch in einem Wort, wenn Sie auf den nächsten Puffern von Daten in Betrieb nehmen).

Solange Sie sicher sind, wird es nur auf einer Multi-Prozessor (Multicore) Maschine verwendet werden, echte Threads ist in Ordnung. Wenn es eine Chance gibt, könnte dies jemals auf einer Single-Core-Maschine durchgeführt werden, würden Sie etwas besser dran, einen einzigen Thread mit überlappenden I / O statt.

Wie andere schon angedeutet haben, wird der Engpass der Disk-I / O. Ich schlage daher vor, dass Sie mich überlappen verwenden / O. Diese im Grunde kehrt die Programmlogik. Anstelle des Codes tyring zu bestimmen, wann zu tun I / O, Sie einfach das Betriebssystem informieren Sie Ihren Code aufrufen, wenn es ein bisschen I / O beendet hat. Wenn Sie I / O-Ports Abschluss , können Sie sogar die sagen, OS mehrere Threads zu verwenden, für die Verarbeitung der Datei chunks.

c-basierte Lösung?

Ich denke, Perl wurde für diesen genauen Zweck geboren.

Strom hat nur einen Cursor. Wenn Sie zu einer Zeit mit mehr als einem Thread auf den Stream zugreifen, werden Sie nicht sicher sein, zu lesen, wo Sie wollen. Lesen Sie wird von der Cursorposition durchgeführt.

Was ich tun würde, ist nur ein Thread haben (vielleicht das wichtigste), die den Strom und den Versand Lesen Bytes zu anderen Threads liest.

Mit dem Beispiel:

  • Thread #i ist bereit und fragen Haupt-Thread es beim nächsten Teil zu geben,
  • Hauptthread nächsten 1MB lesen und ihnen 1 einzufädeln,
  • Thread # i mit der 1MB lesen und zählen Wörter wie Sie wollen,
  • Thread #i beendet seine Arbeit und fragen Sie wieder für den nächsten 1 MB.

Auf diese Weise können Sie Strom-Lese trennen Analyse zu streamen.

Was Sie suchen ist RegEx. Dieser Stackoverflow Thread auf c ++ regex Motoren sollte helfen:

C ++: Was regex Bibliothek sollte ich verwenden

Als erstes bin ich ziemlich sicher, dass C / C ++ ist nicht der beste Weg, dies zu handhaben. Im Idealfall würde man eine Karte verwenden / reduziert für Parallelität auch.

Aber Ihre Zwänge vorausgesetzt, hier ist was ich tun würde.

1) Teilen Sie die Textdatei in kleinere Stücke. Sie dies nicht durch die ersten Buchstaben des Wortes zu tun haben. brechen sie nur bis in etwa 5000-Wort-Brocken. In Pseudo-Code, würden Sie so etwas tun:

index = 0

numworte = 0

mysplitfile = openfile (Index-split.txt)

while (bigfile >> Wort) 

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

2) Verwenden Sie eine gemeinsame Kartendatenstruktur und pThreads neue Threads zu erstellen, jede der Teildateien zu lesen. Auch Pseudo-Code:

maplock = create_pthread_lock ()

sharedmap = std :: map ()

für jeden Index-split.txt-Datei: 

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

dump_map (sharedmap)

void myfunction (Dateiname, 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)

}

Sorry für die Syntax. Ich habe in letzter Zeit viel Python zu schreiben.

Nicht C, und ein bisschen hässlich, aber es dauerte nur 2 Minuten bang:

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

Schleife über jede Zeile mit -n
Split jede Zeile in @F Wörter mit -a
Jedes $_ Wort erhöht Hash %h
Sobald die END von file erreicht,
sort der Hash durch die Frequenz $h{$b}<=>$h{$a}
Wenn zwei Frequenzen identisch sind, alphabetisch sortiert $a cmp $b
Drucken Sie die Frequenz $h{$w} und das Wort $w
Leiten Sie die Ergebnisse in Datei ‚freq‘

lief ich diesen Code auf einer 3.3GB Textdatei mit 580 Millionen Worten.
5.22 Perl in 173 Sekunden abgeschlossen.

Meine Eingabedatei bereits hatte Interpunktion gezupft und Groß in Kleinbuchstaben umgewandelt, dieses Stück Code verwendet:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(Laufzeit von 144 Sekunden)

Die Wortzählung Skript abwechselnd in awk geschrieben werden könnte:
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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top