Filtern Sie die Datei, wenn sich eine Spalte in der Whitelist befindet

725
Hugo Sereno Ferreira

Angenommen, ich habe zwei Dateien, Datei A:

a,abcdef b,bcdefa c,cdefab a,defabc b,efabcd c,fabcde

Und Datei B:

a b

Die Ausgabe, die ich suche, ist:

a,abcdef b,bcdefa a,defabc b,efabcd

Im Grunde möchte ich die Zeilen aus Datei A auswählen, wobei die erste Spalte mit den Werten in Datei B mit Standard-Unix-Befehlen übereinstimmt. Eine Art awk print $1,$2, aber effizienter.

Die erwartete Anzahl von Zeilen in Datei A überschreitet 20 Millionen und Datei B 1 Million. Es muss in O (n) ausgeführt werden, so dass der enthält Schritt wahrscheinlich auf einer Hash - Tabelle verlassen sollte.

2
Das ist eine Datenbank. Daniel R Hicks vor 10 Jahren 2
@DanielRHicks: Sie haben vielleicht Recht, aber OTOH, ich sehe nicht die Notwendigkeit, dass für jeden Beitrag in mit Stackexchange verwandten Websites eine vollständige Erklärung dafür vorliegt, warum der Autor Einschränkungen hat - egal wie absurd diese Einschränkungen erscheinen mögen. Hugo Sereno Ferreira vor 10 Jahren 0

3 Antworten auf die Frage

3
terdon

Dafür gibt es viele Möglichkeiten. Hier sind ein paar, aber mit Perl ist es um Größenordnungen schneller. Ich füge die anderen der Vollständigkeit halber hinzu:

  1. Perl und Haschisch, lächerlich schnell 

    perl -e 'open(A,"fileB"); while(<A>)++}  while(<>){@a=split(/,/); print if defined $k{$a[0]}}' fileA

  2. Gawk und assoziative Arrays, viel langsamer

     gawk ' else}}' fileA fileB

  3. greplächerlich langsam. Sie müssen Ihre fileB leicht modifizieren, damit die Muster nur in der ersten Zeile übereinstimmen

    sed 's/\(.\)/^\1/' fileB > fileC grep -f fileC fileA

Ich habe ein paar Testdateien erstellt und es stellt sich heraus, dass die Perl-Lösungen viel schneller sind als die grep:

$ head -2 fileA GO:0032513_GO:0050129 GO:0050129_GO:0051712 $ head -2 fileB GO:0032513_GO:0050129 GO:0050129_GO:0051712 $ wc -l fileA fileB 1500000 fileA 20000000 fileB $ time perl -e 'open(A,"fileB"); while(<A>)++}  while(<>){@a=split(/,/); print if defined $k{$a[0]}}' fileA > /dev/null   real 0m41.354s user 0m37.370s sys 0m3.960s $ time gawk ' else}}' fileA fileB  real 2m30.963s user 1m23.857s sys 0m9.385s $ time (join -t, <(sort -n fileA) <(sort -n fileB) >/dev/null)  real 8m29.532s user 13m52.576s sys 1m22.029s

Das Perl-Scriptlet kann also eine 20-Millionen-Zeilendatei nach 1,5 Millionen Mustern durchsuchen und in ~ 40 Sekunden enden. Nicht schlecht. Die anderen beiden sind viel langsamer, sie gawkdauerten 2,5 Minuten und die grepeine lief seit über 15 Jahren. Perl gewinnt zweifellos.

+1 für `open (_A _," file_B _ ")`. Wie funktioniert "split (//)"? Ich habe etwas wie "split (/, /)" erwartet. mpy vor 10 Jahren 0
@mpy `split (//)` teilt sich bei jedem Zeichen auf, also wird eine Zeile wie `abcd` zu einem Array` @ a = (a, b, c, d) `, so dass $ a [0]` das erste Zeichen ist . Dies nimmt Muster eines Zeichens an, wie in der Frage beschrieben. terdon vor 10 Jahren 1
2
cYrus

Das sollte den Trick tun:

join -t, <(sort A) <(sort B)
+1 für "join", gute Idee. Ich fürchte, es wird jedoch sehr langsam sein, da beide Dateien zuerst sortiert werden müssen. terdon vor 10 Jahren 0
Das Sortieren einer 20-Millionen-Zeilen-Datei dauert ungefähr 30s auf meinem Computer. cYrus vor 10 Jahren 0
Sehen Sie sich meine aktualisierte Antwort an, der Beitritt und das Sortieren dauert bei meinen Testdateien etwa 8 Minuten, verglichen mit 40 Sekunden für Perl. Ja, jede Sortierung dauert ungefähr eine halbe Minute, aber das erhöht die Laufzeit um mindestens eine Minute. Warum sortierst du auch numerisch? Das erhöht die Laufzeit um einige Sekunden. terdon vor 10 Jahren 0
Ahhh ja, weil ich mit Zahlen getestet habe ... cYrus vor 10 Jahren 0
0
n13

ich verstehe immer noch nicht, was du zu tun versuchst .... du hast schon etwas in einer awk stmt.

grep ist einfach und basiert auf einem sehr effizienten und schnellen Algorithmus, der auf einem Index möglicher Übereinstimmungen basiert. awk führt individuelle Vergleiche durch und prüft, also sollte dies schnell gehen .... awt awk, hier 

 for pat in `cat zfile2` ; do grep -i "$pat," zfile1 ; done;

das funktioniert gut ...

 $ for pat in `cat zfile2` ; do grep -i "$pat," zfile1 ; done; a,abcdef a,defabc b,bcdefa b,efabcd

Hilft das ?

Das Problem bei diesem Ansatz ist, dass es N-mal für N Zeilen in fileB durch fileA "grep" muss. Das wird langsam sein ... terdon vor 10 Jahren 1
yeah , that does add up to O(n2) ... he wants something like O(n) , maybe a O(nlogn) .... but what i didnt understand here is that these days the utilities are quite efficient and are evenly matched in most scenarios ..... i doubt there would be much off a difference in the run time if he did use what he already has in awk ..... You can never be sure unless you analyse the algorithm thats used in the code n13 vor 10 Jahren 0
Hash in Perl sollte zwar +1 für @terdon sein n13 vor 10 Jahren 0
Auch dies wird alle Zeilen zurückhalten, die die Muster von fileA enthalten, nicht nur die Zeilen, die _start_ mit dem Muster sind. terdon vor 10 Jahren 0
he he ..... nope it wont , tested for that !! there is nothing in the output that like : c,fabcde n13 vor 10 Jahren 0
Umm, sorry but it will. You are making the search case sensitive (`-i`) which is probably not wanted and slows the search and you are not specifying that the pattern needs to be at the start of each line. Try this `echo -e "abbb\nbaaa" | grep a`, it will return both lines. If I wanted to be pedantic I could also point out the useless use of cat, `while read pat; do grep ... ;done < fileA` would be better :). terdon vor 10 Jahren 0

Verwandte Probleme