Was wäre bei einer Datei L mit einer nicht-negativen Ganzzahl pro Zeile und Textdatei F ein schneller Weg, um nur die Zeilen in F zu belassen, deren Zeilennummer in Datei L erscheint?
Beispiel:
$ cat L.txt
1
3
$ cat F.txt
Hello World
Hallo Welt
Hola mundo
$ command-in-question -x L.txt F.txt
Hello World
Hola mundo
Ich suche nach einem Befehl, der eine Datei L mit 500 Millionen oder mehr Einträgen verarbeiten kann. Datei L ist numerisch sortiert.
Hinweis: Ich bin auf halbem Weg durch eine Implementierung für eine, command-in-question
aber ich habe mich nur gefragt, ob man möglicherweise auch hier einige Unix-Tools verwenden kann.
Update: Vielen Dank für die Antworten, ich habe heute viel gelernt! Ich würde gerne noch eine Antwort annehmen, aber das ist nicht möglich.
Antworten:
Mit
C
Weglassen aussagekräftige Fehlermeldungen:quelle
xsel -bo | cc -xc - -o cselect
. Und es hat einfach funktioniert - es braucht nur die zwei Bibliotheken.LINE_MAX
, dass Sie Ihre Version erweitert haben, sodass Sie wahrscheinlich mit sehr großen Zeilen in Ihren Dateien arbeiten. Ich habe das A mit einer Version aktualisiert, mit dergetline()
die Zeilengrößenbeschränkung aufgehoben wird.LINE_MAX
, alsogetline
scheint es genau richtig.Ich würde verwenden
awk
, aber nicht den gesamten InhaltL.txt
im Speicher speichern und unnötige Hash-Lookups durchführen ;-).quelle
n
, sonst (wie sie ist) es fehlt1
inL.txt
command-in-question
Skript eingebettet werden soll, der Dateiname nicht in den Code eingebettet werden kann.-v list="$opt_x"
funktioniert auch nicht wegen der Backslash-Verarbeitung, die awk darauf ausführt. Deshalb verwende ich hier stattdessen ENVIRON.grep -n | sort | sed | cut
Das sollte ziemlich schnell gehen (einige zeitgesteuerte Tests sind unten aufgeführt) mit Eingaben jeder Größe. Einige Hinweise, wie:
export LC_ALL=C
./F
gestapelte Datei mit der./L
Lineno-Datei in Einklang zu bringen, müssen wir uns nur um ASCII-[0-9]
Ziffern und den:
Doppelpunkt kümmern .grep -n ''
LINENO:
in den Kopf jeder Zeile in stdin - or ein<./F
.sort -t: -nmk1,1 ./L -
sort
Vernachlässigt das Sortieren seiner Eingabedateien überhaupt und geht stattdessen (korrekt) davon aus, dass sie vorsortiert sind, und-m
fügt sie in-numerically
sortierter Reihenfolge zusammen, wobei grundsätzlich alles ignoriert wird, was über ein eventuell-k1,1
vorkommendes-t:
Doppelpunkt-Zeichen hinausgeht .sort
Gibt einen einzelnen Stream aus, in dem alle Linenos./L
direkt vor den entsprechenden Zeilen stehen./F
../L
Die Zeilen stehen immer an erster Stelle, weil sie kürzer sind.sed /:/d\;n
/:/
Doppelpunktd
übereinstimmt, wird sie aus der Ausgabe entfernt. Andernfalls werden die aktuelle und dien
ext-Zeile automatisch gedruckt .sed
Pflaumensort
‚s Ausgabe nur sequenzielle Leitungspaar , die nicht einen Doppelpunkt und die folgende Zeile passen - oder, um nur eine Zeile aus./L
und dann die nächsten.cut -sd: -f2-
cut
-s
Uppresses von Output die seiner Eingabezeilen, die nicht mindestens einen seiner-d:
Elimiter-Strings enthalten - und so werden./L
die Zeilen komplett beschnitten.:
Doppelpunkte getrenntes-f
Feldcut
weg - und so geht es mit allen von ihnengrep
eingefügten Linenos.kleiner Eingangstest
... generiert 5 Zeilen Sample-Input. Dann...
... druckt ...
größere zeitgesteuerte Tests
Ich habe ein paar ziemlich große Dateien erstellt:
... die 5mil Zeilen in
/tmp/F
und 1,5mil zufällig ausgewählte Zeilen davon in setzen/tmp/L
. Ich habe dann gemacht:Es druckte:
(Ich habe die Backslashes dort hinzugefügt)
Unter den derzeit hier angebotenen Lösungen ist dies die schnellste von allen, außer einer, wenn sie mit dem oben auf meinem Computer generierten Datensatz verglichen wird. Von den anderen wäre nur einer beinahe um den zweiten Platz gekämpft, und das ist meuhs
perl
hier .Dies ist keineswegs die ursprüngliche Lösung, die angeboten wird. Dank der Ratschläge und Anregungen anderer konnte die Ausführungszeit um ein Drittel verkürzt werden. Informationen zu langsameren Lösungen finden Sie im Post-Verlauf (aber warum?) .
Es ist auch erwähnenswert, dass einige andere Antworten möglicherweise besser miteinander konkurrieren, wenn nicht die Multi-CPU-Architektur meines Systems und die gleichzeitige Ausführung der einzelnen Prozesse in dieser Pipeline berücksichtigt würden. Sie arbeiten alle zur gleichen Zeit - jeder auf seinem eigenen Prozessorkern - und geben die Daten weiter und erledigen ihren kleinen Teil des Ganzen. Es ist ziemlich cool.
aber die schnellste lösung ist ...
Aber es ist nicht die schnellste Lösung. Die schnellste Lösung, die hier zweifellos angeboten wird, ist das C-Programm . Ich habe es genannt
cselect
. Nachdem ich es in meine X-Zwischenablage kopiert habe, habe ich es wie folgt kompiliert:Ich habe dann gemacht:
... und die Ergebnisse waren ...
quelle
sed -ne'/:/!{n;p;}' | cut -d: -f2-
stattsed -ne'/:/!N;/\n/s/[^:]*://p'
sed
s wechseln - das, wassed
ich verwende, ist das Erbstücksed
- Sie können denalias
Wert in dentime
Ergebnissen sehen. Mein Erbstück-Paket ist übrigens statisch gegen eine musl libc kompiliert - die Regex-Implementierung, für die TRE verwendet wird . Wenn ich es auf GNU umschaltesed
- und ohnecut
es auszuführen -, erhöht es die Fertigstellungszeit (2,8 Sekunden) um eine volle Sekunde - und addiert es um mehr als ein Drittel. Und das ist nur 0,3 Sekunden schneller als bei Ihnen auf meinem System.sort -mn
im gegensatz zusort -nmk1,1
könnte besser sein, da Sie nicht die Aufteilung hier tun müssen (nicht getestet)-n
ist spezifiziert, nur um die erste numerische Zeichenfolge in einer Zeile zu machen, also dachte ich mir, ok-mn
oder-nm
und, aus welchem Grund auch immer, das einzige Mal, wenn es in der Abschlusszeit unter 2 Sekunden sank, war, als ich in allen Optionen hinzufügte, wie es ist. Es ist seltsam - und es ist der Grund, warum ich gestern überhaupt nicht darüber nachgedacht habe-m
- ich wusste, worum es mir ging, aber es schien nur als eine Art Autooptimierungssache zu funktionieren. Interessanterweise hat das Erbstücksort
eine-z
String-Länge-Option, die nur für-[cm]
... gilt-n
ist nicht die erste numerische Zeichenfolge in der Zeile . Es betrachtet die Linie nur als eine Zahl, alsoabc 123
wäre es 0. Es kann also nicht weniger sein effizient sein als mit-t: -k1,1
Ich würde verwenden
awk
:Update: Ich habe Leistungsmessungen durchgeführt. Es scheint, dass diese Version bei sehr großen Datenmengen noch besser skaliert (wie es bei den angegebenen Anforderungen der Fall ist), da der Vergleich sehr schnell ist und den zum Aufbau der Hash-Tabelle erforderlichen Aufwand überkompensiert.
quelle
awk
Möglicherweise sind nicht alle s in der Lage, mit so großen Datenmengen umzugehen. - Ich benutze GNUawk
und es gibt keine Probleme; Der Test mit 500 Millionen Datenzeilen dauerte 7 Minuten.real 16m3.468s
-user 15m48.447s
-sys 0m10.725s
. Es wurden 3,3 GB RAM verwendet, um eine 1/10 GrößeL
mit 50.000.000 Zeilen zu testen . undF
mit 500.000.000 Zeilen - gegen Zeit für Stéphane Chazelas 'awk anser:real 2m11.637s
-user 2m2.748s
-sys 0m6.424s
- Ich benutze keine schnelle Box, aber der Vergleich ist interessant.seq
ausgegeben und dann eine kleine, zufällig ausgewählte Untergruppe von derselben in L .Der Vollständigkeit halber: Wir können das ausgezeichnete awk-Skript in der Antwort von Stéphane Chazelas und das Perl-Skript in der Antwort von kos zusammenführen, ohne jedoch die gesamte Liste im Gedächtnis zu behalten, in der Hoffnung, dass Perl möglicherweise schneller ist als awk. (Ich habe die Reihenfolge der Argumente geändert, um sie mit der ursprünglichen Frage abzugleichen.)
quelle
awk
. Es ist ungefähr so schnell wie meins - ich habe beide Tests gerade drei Mal durchgeführt und jedes Mal habe ich meinen 5-mil-Leitungstestsatz in 1,8 ... Sekunden und Ihren 1,9 ... Sekunden bearbeitet. Der getestete Code ist in meiner Antwort, wenn es Sie interessiert, aber der Punkt ist, dass es sehr gut ist. Außerdem ist die Ausgabe korrekt - ich kann dieawk
Arbeit immer noch nicht erledigen ... Trotzdem werden unsere beiden Antworten von FloHimselfs beschämt .awk
s haben. Auf Ihrer Probe erhalte ich 1,4s mit gawk (4s für Janis '), 0,9s mit mawk, 1,7s mit dieser Perl-Lösung, 2,3s mit kos', 4,5s mit Ihrer (GNU sed) und 1,4s mit Ihrer ( GNU sed) und meine Verbesserungsvorschläge (und 0,5s für die C-Lösung).Ich habe dazu ein einfaches Perl-Skript geschrieben:
Usage: script.pl inputfile_f inputfile_f
F.txt
L.txt
L.txt
in einem ArrayF.txt
zeilenweise und verfolgt dabei die aktuelle Zeilennummer und den aktuellen Array-Index. erhöht dieF.txt
aktuelle Zeilennummer; Wenn dieF.txt
aktuelle Zeilennummer mit dem Inhalt des Arrays am aktuellen Arrayindex übereinstimmt, wird die aktuelle Zeile gedruckt und der Index erhöhtKosten- und Komplexitätsaspekte :
In Anbetracht der Kosten für die Ausführung der Aufgaben, der Kosten für die Durchführung der Vergleiche und der Kosten für das Drucken der Zeilen, wobei N 1 als Anzahl der Zeilen
F.txt
und N 2 als Anzahl der Zeilen angegeben wird, läuftL.txt
diewhile
Schleife höchstens N 1- mal. führt zu 2N 1 + N 2 -Zuweisungen (offensichtlich unter der Annahme, dass N 1 > N 2 ist ), zu 2N 1 -Vergleichen und zu N 2 -Drucken; Wenn die Kosten für jede Operation gleich sind, betragen die Gesamtkosten für die Ausführung derwhile
Schleife 4N 1 + 2N 2 , was zu einer Komplexität des Skripts von O (N) führt.Test mit einer Eingabedatei mit 10 Millionen Zeilen :
Verwenden einer 10-Millionen-Zeilen-
F.txt
Datei mit zufälligen Zeilen von 50 Zeichen Länge und einer 10-Millionen-Zeilen-L.txt
Datei mit Zahlen von 1 bis 10000000 (Worst-Case-Szenario):quelle
Diese Perl-Lösung ist um etwa 20% schneller als die anderen awk- oder perl-Lösungen, jedoch offensichtlich nicht so schnell wie die Lösung in C.
quelle
Da L.txt sortiert ist, können Sie join verwenden. Nummerieren Sie einfach jede Zeile in F.txt, verbinden Sie die beiden Dateien und entfernen Sie die Zeilennummer. Es werden keine großen Zwischendateien benötigt.
Tatsächlich werden Ihre Datenleitungen durch das oben beschriebene Verfahren entstellt, indem der gesamte Leerraum durch ein einzelnes Leerzeichen ersetzt wird. Um die Zeile intakt zu halten, müssen Sie als Trennzeichen ein Zeichen wählen, das in Ihren Daten nicht vorkommt, z. B. "|". Der cmd ist dann
Das erste sed entfernt führende Leerzeichen aus der Ausgabe von "cat -n" und ersetzt den Tabulator. Der zweite Satz entfernt die Zeilennummer und "|".
quelle
join L.txt <(nl F.txt )
aber es funktioniert nicht bei großen Dateien. Willkommen auf der Seite, es kommt übrigens nicht oft vor, dass wir von neuen Nutzern so klare und gut formatierte Antworten erhalten!join
/comm
kann nicht arbeiten mit numerisch sortiert Eingabe.join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-
- es war langsam! - und selbst wenn ich vorbereitete Dateien mit geeigneten, mit 0 aufgefüllten Schlüsseln eingespeist habejoin -t' ' L.txt F.txt | cut -d' ' -f2-
, war es immer noch langsam (ohne die Vorbereitungszeit) - langsamer als dieawk
Antwort von @Janis (wo ich einen Kommentar zu den tatsächlichen Zeiten für beide gepostet habe) seine und @ StéphaneChazelas Antwortjoin
+awk printf
Prozessersetzung warreal 20m11.663s user 19m35.093s sys 0m10.513s
gegen Stéphane Chazelas 'real 2m11.637s user 2m2.748s sys 0m6.424s
mitL
50 Millionen Zeilen,F
500 Millionen Zeilen.Der Vollständigkeit halber noch ein
join
Lösungsversuch:Dies funktioniert, indem die Spalte mit der Zeilennummer, die verbunden wird, als feste Länge mit führenden Nullen formatiert wird, sodass die Zahlen immer 15 Stellen lang sind. Dies umgeht das Problem, dass Verknüpfungen die normale numerische Sortierreihenfolge nicht mögen, da die Spalte nun effektiv als Wörterbuchsortierung verwendet werden muss.
nl
wird verwendet, um Zeilennummern in diesem Format zu F.txt hinzuzufügen.sed
Muss leider zur Neuformatierung der Nummerierung in L.txt verwendet werden.Dieser Ansatz scheint bei den mit der @ mikeserv-Methode generierten Testdaten in Ordnung zu sein. Aber es ist immer noch sehr langsam - die c-Lösung ist auf meinem Computer 60x schneller. etwa 2/3 der Zeit wird in
sed
und 1/3 in verbrachtjoin
. Vielleicht gibt es einen besseren sed Ausdruck ...quelle
nl
super cool, aber Sie können es nicht zuverlässig für ungetestete Eingaben verwenden. Eines der Dinge, die es so cool machen, ist der logische Seitenbegrenzer-d
. Wenn eine Eingabezeile standardmäßig nur aus den Zeichenfolgen:\`
(aber ohne das nachfolgende Grab) 1, 2, 3 oder 3 Mal hintereinander besteht, werden Ihre Zählungen etwas verrückt. Experimentieren Sie mit - es ist ziemlich ordentlich. Sehen Sie sich vor allem an, was passiert, wenn nl` eine Zeile mit 1 Trennzeichen und später eine weitere mit 3 oder 2Da die akzeptierte Antwort in C ist, dachte ich, es ist in Ordnung, hier eine Python-Lösung zu werfen:
Wenn Sie eine externe Bibliothek wie numpy verwenden, sieht eine Lösung noch eleganter aus:
quelle