noqqe


blog | sammelsurium | projects | about

GNU Coreutils

2014-03-25 @ admin, bash, coreutils, csv, flatfile, for, gnu, grep, id, iowait, join, shell, time

Man stelle sich folgendes Szenario vor. Eine große CSV Datei enthält Datensätze. Eine weitere Datei enthält ~1,5mio IDs die ein Subset der Datensätze darstellen. Gewünscht ist ein File das alle Datensätze des Subsets enthält.

for-loop grep

Die gewohnte Pauschallösung für derartige Probleme. Ganz im Bash-Admin-Stil

$ time for x in $(cat idsubset.txt) ; do
>  grep ^$x dataset.csv
> done > result.csv

Nur leider kommen dabei ganze 1,5 Records pro Sekunde heraus, was alles in allem in über 2 Wochen Rechenzeit endet. IOwait enstand dabei nicht.

GNU parallel

16 Core-Maschine. Einfach härter parallel greppen. GNU parallel hatte ich 2012 einmal ausprobiert.

$ cat idsubset.txt | time parallel 'grep -m 1 ^{} dataset.csv' > result.csv
[...]
Command terminated by signal 2
13165.04user 56967.06system 1:23:04elapsed 1406%CPU (0avgtext+0avgdata 40816maxresident)k

Nach knapp 90 Minuten war das gute Stück bei ca. 80% des Files angekommen. Annehmbar, auch wenn die Cores und der RAM der Kiste damit gut beschäftigt waren.

join

Das effizienteste war allerdings join aus den GNU core utilities

$ sort idsubset.txt > sidsubset.txt
$ sort dataset.csv > sdataset.csv
$ time join sidsubset.txt sdataset.csv > result.txt
[...]
real    0m38.965s
user    0m36.290s
sys     0m0.991s

Fucking 38 Sekunden. Zwei Dinge sind zu beachten. Sortierung und Formatierung.

Das Field, das zusammengeführt werden soll muss in beiden Files über den gleichen Trenner identifizierbar sein. Zurecht-ge-sed-et©

Beide Files müssen alphabetisch sortiert sein, nicht numerisch. Das ist im wesentlichen dem Algorithmus geschuldet der in join verbaut ist. Linecounts anstelle von Fullscans bei jeder Iteration sind der Trick.

BigData Krams? Lolo. Fucking Coreutils.

Comments (11)

Anonymous on 2014-03-25T19:45:25.850672
Is it an ASCII key? If so you might speed up the join(1) solution further by first doing LC_ALL=C join ...

raimue on 2014-03-25T19:56:52.598101
Fuck Coreutils. ;-) Mein Vorschlag ist POSIX-kompatibel: $ grep -f

noqqe on 2014-03-25T20:13:29.863577
Yep, its an ASCII key. Does this really speed the join command up? I will give it a try

noqqe on 2014-03-25T20:15:18.452960
woah, coole Idee. Denk das probier ich auch mal aus. Mit dem Stdin bin ich mir net sicher, vielleicht mal ichs mal mit Bracket im File reingesedet. Danke! :)

Clemens on 2014-03-25T20:29:48.625541
Process Substitution ist nicht Teil von POSIX, aber mit mkfifo kann man sich da schon drum rum mogeln.

raimue on 2014-03-25T22:32:19.291227
Okay, da hast du recht. Dann könnte man es auch mit einer temporären Datei lösen. Wieso hat das Isso eigentlich meine ^ verschluckt? Anscheinend mag es die nur nicht, wenn sie in Quotes stehen: "^"

noqqe on 2014-03-26T09:19:26.455401
ich lass das gerade laufen... es sieht nicht gut aus ... 10GB RAM für den einen grep Prozess, der schon gut 5 Minuten läuft.

noqqe on 2014-03-26T10:03:57.187671
macht keinen Sinn. Hab nach 50 Minuten abgebrochen. time grep -f idsubset.txt dataset.txt result.txt real 53m5.481s user 52m47.950s sys 0m16.190s

waldner on 2014-03-30T21:29:57.230860
Ich schlage awk vor. Es hängt vom Datenformat ab, aber awk sollte die leistungsfähigste und schnellste Lösung sein (und ohne die Dateien zu sortieren). ZB, wenn die ID das vierte CSV Feld von "dataset.txt" ist, kann man tun: awk -F, 'NR==FNR{a[$4]; next} $4 in a' idsubset.txt dataset.txt Natürlich soll man das an das konkrete Datenformat anpassen.

waldner on 2014-03-31T16:01:56.729736
Sorry, das muss sein: awk -F, 'NR==FNR{a[$0]; next} $4 in a' idsubset.txt dataset.txt das setzt voraus, dass jede Zeile von "idsubset.txt" eine ID ist, und dass IDs im vierten Feld von "dataset.txt" gesucht werden müssen. Mit LC_ALL=C awk -F, 'NR==FNR{a[$0]; next} $4 in a' idsubset.txt dataset.txt  sollte es noch schneller laufen.

David on 2014-05-19T11:27:14.609332
"Pauschallösung"!? *Niemals* "for ... in $(cat ...)" für das Zeilenweise lesen von Dateien benutzen. Dafür gibts while read line; do [COMMAND]; done