rasputin53
Anmeldungsdatum: 13. Oktober 2016
Beiträge: 4
|
Hallo zusammen, Ich bin Anfänger, was Linux und Programmieren angeht, und habe eine Frage zur Suche mehrerer strings aus einer Datei in einer anderen.
Im Prinzip habe ich das Problem gelöst, indem ich grep verwende (s.u.), aber das Ganze ist seeehr langsam, weil die zu durchsuchende Datei recht groß ist (Tabelle in Textform, ca. 300 MB). Mein verwendeter Befehl lautet: | grep -f Input.txt Data.txt > Output.txt
|
Beispielhaft zeige ich hier zwei Zeilen aus der Input.txt. Die "Tabelle" hat nur eine Spalte und einige tausend Zeilen: AL-6-port-124578531 In der Data.txt steht eine Menge in über 50 Spalten und in der letzten - nennen wir sie mal Spalte 51 - steht evtl. derselbe Text wie in einer der Zeilen aus Input.txt. Der Text in der einen Spalte der Input.txt und der Spalte 51 der Data.txt ist entweder komplett identisch (dann will ich ihn haben) oder die Zeile interessiert mich nicht. Beim Testen habe ich festgestellt, dass der Server nur etwa 1.000 Zeilen pro Stunde in die Output.txt schreibt. Das kommt mir etwas zu langsam vor, da ich etwa 40.000 Zeilen insgesamt erwarte. Daher meine Frage: Hat jemand eine Idee, wie ich das Ganze beschleunigen kann? Wäre awk vielleicht schneller? Oder kann ich grep irgendwie beschleunigen? Ich dachte immer, grep sei ziemlich schnell. Oder hat der Server gerade einfach ein Geschwindigkeitsproblem und das Ganze sollte eigentlich auch so viel schneller gehen?! Gruß, rasputin53
|
frostschutz
Anmeldungsdatum: 18. November 2010
Beiträge: 7651
|
300MB Text durchzuackern braucht eben seine Zeit. Tabellen in Textform sind nicht effizient. Vielleicht magst du dich mal mit Datenbanken (sqlite o.ä.) auseinandersetzen. Ein Index auf die gewünschte Spalte erstellen und die Abfrage sollte im Sekundenbruchteil möglich sein.
Wäre awk vielleicht schneller?
Ist möglich wenn awk seinen Stringvergleich nur direkt auf die betreffende Spalte anwenden muss statt wie grep querbeet auf alles. Am Ende kommt es darauf an, ob grep an der CPU hängt, oder am I/O. Wobei 300MB, wenn die Kiste entsprechend viel RAM hat, ja spätestens beim zweiten Aufruf dann schon im RAM hängen.
Oder hat der Server gerade einfach ein Geschwindigkeitsproblem und das Ganze sollte eigentlich auch so viel schneller gehen?!
Das musst du uns sagen ... vServer können manchmal sehr sehr langsame I/O haben. Wenn die Festplatte nut 50kb/s liefert ist es unschön...
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12802
|
rasputin53 schrieb:
Im Prinzip habe ich das Problem gelöst, indem ich grep verwende (s.u.), aber das Ganze ist seeehr langsam, weil die zu durchsuchende Datei recht groß ist (Tabelle in Textform, ca. 300 MB).
Naja, 300MB sind nicht wirklich sooo viel. Was bedeutet denn "seeehr langsam"?
Beispielhaft zeige ich hier zwei Zeilen aus der Input.txt. Die "Tabelle" hat nur eine Spalte und einige tausend Zeilen: AL-6-port-124578531
Ich sehe nur eine Zeile.
In der Data.txt steht eine Menge in über 50 Spalten und in der letzten - nennen wir sie mal Spalte 51 - steht evtl. derselbe Text wie in einer der Zeilen aus Input.txt. Der Text in der einen Spalte der Input.txt und der Spalte 51 der Data.txt ist entweder komplett identisch (dann will ich ihn haben) oder die Zeile interessiert mich nicht.
D.h. Teilmatches sind uninteressant? Dann wäre awk vermutlich ein besseres Tool. Dann kannst Du so filtern: | awk 'BEGIN {while(getline <"Input.txt") text[$0]=1} text[$NF] {print "found: " $0}' Data.txt
|
Beim Testen habe ich festgestellt, dass der Server nur etwa 1.000 Zeilen pro Stunde in die Output.txt schreibt. Das kommt mir etwas zu langsam vor, da ich etwa 40.000 Zeilen insgesamt erwarte.
Ja, dann hast Du ein IO-Problem, scheint mir.
Hat jemand eine Idee, wie ich das Ganze beschleunigen kann?
Du kannst fgrep statt grep nehmen. Du hast ja wohl keine Regulären Ausdrücke als Suchmuster.
Wäre awk vielleicht schneller?
Das vielleicht nicht, aber präziser (s.o.).
Oder kann ich grep irgendwie beschleunigen? Ich dachte immer, grep sei ziemlich schnell.
Ja, ist es. fgrep wäre in Deinem Fall vermutlich schneller, aber s.u.
Oder hat der Server gerade einfach ein Geschwindigkeitsproblem und das Ganze sollte eigentlich auch so viel schneller gehen?!
Die Sache ist höchstwahrscheinlich IO-gebunden - da wird die Wahl eines anderen Programms eher nicht helfen.
|
wxpte
Anmeldungsdatum: 20. Januar 2007
Beiträge: 1140
Wohnort: Schäl Sick
|
rasputin53 schrieb: Beim Testen habe ich festgestellt, dass der Server nur etwa 1.000 Zeilen pro Stunde in die Output.txt schreibt. Das kommt mir etwas zu langsam vor, da ich etwa 40.000 Zeilen insgesamt erwarte.
Mir kommt das nicht sonderlich langsam vor: Im Prinzip habe ich das Problem gelöst, indem ich grep verwende (s.u.), aber das Ganze ist seeehr langsam, weil die zu durchsuchende Datei recht groß ist (Tabelle in Textform, ca. 300 MB). Mein verwendeter Befehl lautet: | grep -f Input.txt Data.txt > Output.txt
|
Beispielhaft zeige ich hier zwei Zeilen aus der Input.txt. Die "Tabelle" hat nur eine Spalte und einige tausend Zeilen:
Du lässt also eine Datei von ca. 300 MB Größe nach mehreren tausend Mustern durchsuchen? Mit anderen Worten: auf jede Zeile der Data.txt werden alle "einige tausend" Zeilen der Input.txt angewendet. Wenn man das miteinander multipliziert... Nun kenne ich die Suchlogik von grep -f nicht so genau, und weiß daher nicht, ob erst alle Muster der Input.txt angewendet werden, bevor zur nächsten Zeile der Data.txt gesprungen wird, oder ob erst die gesamte Datei durchsucht wird, bevor zum nächsten Muster gesprungen wird. Unter der Voraussetzung, dass es sich bei den Mustern in Input.txt um einen Schlüssel handelt, der jeweils in der Gesamtdatei nur in einer einzigen Zeile vorkommt, würde ich daher wie folgt vorgehen:
| while read z
do
fgrep -m 1 $z Data.txt >> Output.txt
done < Input.txt
|
Wie rklm schon schrieb, ist bereits die Verwendung von fgrep schneller, als grep . Das Entscheidende ist aber, dass durch Verwendung der Option -m 1 der Suchlauf nach dem ersten Treffer gestoppt wird, und danach sofort mit dem nächsten Muster weitergesucht wird, anstatt zunächst die Datei (sinnlos) bis zum Ende nach weiteren Treffern zu durchsuchen. Edit: Soeben habe ich gesehen, dass du einerseits von "einigen tausend" Zeilen in der Input.txt schreibst, andererseits aber ein Ergebnis von "etwa 40.000 Zeilen" erwartest. Anscheinend gehst du also von mehreren Treffern pro Suchmuster aus. Somit eignet sich mein Tipp mit der Option -m 1 nicht für deine Zwecke.
|
Seebär
Anmeldungsdatum: 2. Mai 2009
Beiträge: 829
|
rasputin53 schrieb: Hat jemand eine Idee, wie ich das Ganze beschleunigen kann?
Ja, mal abgesehen von einem besseren Verfahren: Parallelisierung! Zerlege deine "input.txt" (besser wäre ja auch der Name "suchwerte") in n Blöcke und starte n Prozesse parallel (mit & im Hintergrund und dann wait), am Ende deren Ergebnisse (Treffer) dann einfach wieder vereinen. Wenn das Ganze nicht zu sehr IO-gebunden ist (ich glaube das es keine IO-Thematik ist, aber so was kann man auch schon mit top prüfen, da auch mal die "1" für Detail je CPU je drücken und Anzeigen zu us/wa beobachten), dann sollte das bei entsprechender #Cores erheblich schneller werden.
|
frostschutz
Anmeldungsdatum: 18. November 2010
Beiträge: 7651
|
Zerlege deine "input.txt" (besser wäre ja auch der Name "suchwerte") in n Blöcke
Also wenn, dann müsstest du die data.txt zerlegen. Ansonsten wird es nur langsamer weil du die 300MB data.txt nicht einmal sondern zehnmal durchackern musst. Aber wahrscheinlich ist der Hase eh ganz woanders begraben
|
track
Anmeldungsdatum: 26. Juni 2008
Beiträge: 7174
Wohnort: Wolfen (S-A)
|
rasputin53 schrieb: In der Data.txt steht eine Menge in über 50 Spalten und in der letzten - nennen wir sie mal Spalte 51 - steht evtl. derselbe Text wie in einer der Zeilen aus Input.txt. Der Text in der einen Spalte der Input.txt und der Spalte 51 der Data.txt ist entweder komplett identisch (dann will ich ihn haben) oder die Zeile interessiert mich nicht.
Haben die anderen ja schon gesagt: grep geht sicherlich, aber awk (→ Vergleich der Muster nur mit Spalte 51) ist genauer. Was die Verarbeitungszeit angeht, ist das alles ± egal, denn der reine I/O ist bei beiden gleicht: 1x die beiden Dateien lesen. Mehr ist es nicht, so oder so. Und das läuft mit 1...300 MByte/s, je nach Anbindung der Festplatte. (1 MByte/s wäre z.B. ein uraltes 10 MBit-Netzwerk oder ein USB-Stick der 1.Generation) Der Overhead von grep oder awk ist auch nicht so enorm. Derzeit habe ich z.B. mit awk (was das Langsamere sein dürfte) eine solche CSV- Datei von 40 Spalten und 4 Mill. Zeilen umgefiltert, und das dauerte auf meinem alten 1GHz- Athlon ± 3 Minuten.
Beim Testen habe ich festgestellt, dass der Server nur etwa 1.000 Zeilen pro Stunde in die Output.txt schreibt. Das kommt mir etwas zu langsam vor, da ich etwa 40.000 Zeilen insgesamt erwarte.
... also ist da mit Deinem System (dem Server oder wer immer da bremst) etwas ganz gründlich im Argen - wie ja auch meine Vorredner schon sagten. Vielleicht verrätst Du uns etwas mehr über Dein System, und wie es angebunden ist. - mangels funktionierender Kristallkugel können wir Dir sonst nämlich auch nicht weiterhelfen ... 😉 LG, track
|
seahawk1986
Anmeldungsdatum: 27. Oktober 2006
Beiträge: 11176
Wohnort: München
|
wxpte schrieb: Unter der Voraussetzung, dass es sich bei den Mustern in Input.txt um einen Schlüssel handelt, der jeweils in der Gesamtdatei nur in einer einzigen Zeile vorkommt, würde ich daher wie folgt vorgehen:
| while read z
do
fgrep -m 1 $z Data.txt >> Output.txt
done < Input.txt
|
Das ist im Vergleich zur Lösung mit awk extrem langsam - um das mal grob zu Benchmarken:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | #!/bin/bash
rm -f Input.txt Data.txt
for n in {0..40000}; do
pwgen -1 -s 20 51 | xargs echo -n >> Data.txt
printf "\n" >> Data.txt
done
last_columns=($(cut -d " " -f 51 Data.txt))
for i in {1..10000}; do
printf "%s\n" ${last_columns[$RANDOM]} >> Input.txt
done
unset last_columns
rm -f {a,f}Output.txt
time awk 'BEGIN {while(getline <"Input.txt") text[$0]=1} text[$NF] {print $0}' Data.txt > aOutput.txt
time while read z; do fgrep -m 1 "$z" Data.txt >> fOutput.txt; done < Input.txt
time test.py
|
./compare_awk_fgrep.sh
real 0m0.118s
user 0m0.083s
sys 0m0.033s
real 1m46.847s
user 1m9.847s
sys 0m18.963s
Der Ansatz von rasputin53 sprengt in meiner VM mit einem Gigabyte freiem RAM vor der Ausführung des Skripts und ohne SWAP das Speicherlimit - eventuell fängt sein Server da einfach zu Swappen an.
|
track
Anmeldungsdatum: 26. Juni 2008
Beiträge: 7174
Wohnort: Wolfen (S-A)
|
Vielleicht einfach mal ein systematischer Ansatz: Verrat uns doch mal, wie groß Deine beiden Dateien tatsächlich sind, und wie schnell Dein System die liest: und - Poste doch bitte mal, was der "Word Count" und die dazu benötigte Zeit genau ergibt. Dann haben wir wenigstens mal einen konkreten Anhalt ! LG, track
|
rasputin53
(Themenstarter)
Anmeldungsdatum: 13. Oktober 2016
Beiträge: 4
|
Erst einmal vielen Dank für die ausführlichen Antworten. Ja, zugegeben, es sollten 2 Beispielzeilen sein. Ist aber unerheblich. Das Prinzip ist ja deutlich geworden. Ich werde es mal testweise auf meinem eigenen PC mit grep und awk ausprobieren, um die Geschwindigkeit zu vergleichen. Zu dem Server kann ich gerade leider gar nicht viel sagen. Er hat ca. 48 GB RAM und grep hat etwa 1,6 davon in Gebrauch gehabt. Ich werde morgen noch etwas herumprobieren mit den vielen Vorschlägen und mal einen Performance-Test machen. Melde mich demnächst wieder!
|
user_unknown
Anmeldungsdatum: 10. August 2005
Beiträge: 17548
Wohnort: Berlin
|
rasputin53 schrieb:
Im Prinzip habe ich das Problem gelöst, indem ich grep verwende (s.u.), aber das Ganze ist seeehr langsam, weil die zu durchsuchende Datei recht groß ist (Tabelle in Textform, ca. 300 MB).
Zu meinen Fragen gehört auch, wie groß denn eine Zeile ist. Etwa 50x strlen ("AL-6-port-124578531")? Wie oft wirst Du das machen müssen - 1x oder wiederholt? Wachsen die Dateien zwischenzeitlich, beide, nur eine? Kommt es bei den Ergebnissen auf die Reihenfolge an? Wenn nicht, dann könnte man beide Dateien nach dem Schlüssel sortieren und nur 1x gespreizt durch beide Dateien durchgehen, also immer auf der Seite eine Zeile weiterspringen, die kleiner als die andere ist. Wenn die Dateien nicht umsortiert werden dürfen könnte man trotzdem eine Kopie der Dateien erzeugen, in die man zusätzlich die Originalzeilennummer schreibt. Die 300 MB einmalig einzudampfen sollte deutlich was bringen, wenn das Ergebnis dann nur noch 6 MB groß ist und nicht 49 Spalten verglichen werden, die einen gar nicht interessieren. Was ist denn der Trenner zwischen den Spalten, oder sind die Spalten nur durch die Position in der Datei definiert?
Beispielhaft zeige ich hier zwei Zeilen aus der Input.txt. Die "Tabelle" hat nur eine Spalte und einige tausend Zeilen:
300 Mio. * 5.000 ist 1,5 Billionen Vergleichsvorgänge.
In der Data.txt steht eine Menge in über 50 Spalten und in der letzten - nennen wir sie mal Spalte 51 - steht evtl. derselbe Text wie in einer der Zeilen aus Input.txt. Der Text in der einen Spalte der Input.txt und der Spalte 51 der Data.txt ist entweder komplett identisch (dann will ich ihn haben) oder die Zeile interessiert mich nicht.
In den anderen 50 Spalten matcht der Text nie? Ist es nicht wirklich die letzte Spalte? Das könnte einen großen Unterschied machen, ob grep in jeder Zeile bei jedem Zeichen zu vergleichen ansetzt, oder ob man grep gleich auf die richtige Position ansetzen kann.
Wäre awk vielleicht schneller?
Die Fragen wären im Wesentlichen die gleichen. Alles in eine Datenbank pumpen, indizieren und die Datenbank machen lassen ist auch eine elegante Lösung, aber für eine Suche die sich nicht wiederholen wird und wenn Du keine Erfahrung mit relationalen Datenbanken hast, wird der Arbeitsoverhead wohl zu groß.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12802
|
seahawk1986 schrieb: wxpte schrieb: Unter der Voraussetzung, dass es sich bei den Mustern in Input.txt um einen Schlüssel handelt, der jeweils in der Gesamtdatei nur in einer einzigen Zeile vorkommt, würde ich daher wie folgt vorgehen:
| while read z
do
fgrep -m 1 $z Data.txt >> Output.txt
done < Input.txt
|
Das ist im Vergleich zur Lösung mit awk extrem langsam - um das mal grob zu Benchmarken:
Das sieht man auf den ersten Blick, denn das ist O(n * m) anstatt O(n) (n = Zeilen, m = Suchwörter). Selbst, wenn die Datei tatsächlich nur ein Mal von der Platte gelesen wird, ist der Overhead erheblich, weil immer wieder die gesamte Datei durchsucht wird.
|