Ich habe eine große Textdatei (1,5 G),
Ich möchte wissen, was das schnellste und zuverlässigste Tool unter Linux ist.
Ich benutze normalerweise:
awk '!x[$0]++' file.txt
Aber wenn ich den htop
Befehl benutze, sehe ich, dass meine Speichernutzung zunimmt.
Ich möchte wissen, was das schnellste und zuverlässigste für große Dateien ist.
uniq?
sort?
sed?
awk?
Warum?
time
?Antworten:
Betrachten wir, wie jede Lösung funktioniert.
uniq
Dies setzt voraus, dass die Datei bereits sortiert ist. Wenn nicht, müssen Sie essort
zuerstsort
durchleiten , was bedeutet, dass Sie die gesamte Datei in den Speicher lesen, neu anordnen (O(n log n)
) und dann in die Pipe schreiben müssen. Die Arbeit vonuniq
ist sehr billig, da nur benachbarte Zeilen seiner Eingabe verglichen werden müssen.sort -u
Dies kombiniert die Arbeit vonsort | uniq
. Dies muss alle eindeutigen Eingaben im Speicher sammeln, wie es dasawk
Skript tut, aber es verschwendet auch Zeit, sie zu sortieren, bevor die Ausgabe erzeugt wird. Dies istO(n log n)
, obwohl in diesem Falln
die Anzahl der eindeutigen Elemente nicht alle Eingaben sind. Also ist es besser als die Pfeife.sed
Ich bin mir nicht sicher, warum Sie dies aufgelistet haben, da ich mir überhaupt keinen guten Weg vorstellen kann, dies zu tunsed
. Wenn Sie es zuerst sortieren und zu einemsed
Skript weiterleiten, können Sie möglicherweise benachbarte Zeilen vergleichen. Sosed
würde nur tun , was deruniq
Fall ist, unduniq
wahrscheinlich tut es um so effizient wie möglich.awk
Dies ist wahrscheinlich das Beste, da nur der minimale Arbeitsaufwand erforderlich ist. Beim Lesen jeder Zeile wird eine effiziente Hash-Suche durchgeführt, um festzustellen, ob sich die Zeile bereits in ihrem Speicher befindet, und nur die eindeutigen Zeilen als Hash-Schlüssel und ein Zähler als Wert gespeichert. (Wenn die Zeile zuvor nicht vorhanden war, ist die Bedingung erfüllt, sodass die Zeile gedruckt wird. Andernfalls wird dies nicht der Fall sein.) Dies verwendetO(n)
Zeit undO(uniq n)
Speicher.Jede Methode benötigt eine beträchtliche Menge an Speicher, entweder um die Eingabe zu sortieren oder um zu verfolgen, welche Eingaben gesehen wurden, damit Duplikate entfernt werden können.
quelle
awk
dazu erklärt auch, warum immer mehr Speicher verwendet wird. Alles, was eine Sortierung durchführt, wird dies auch tun. Nur 1) es wird wahrscheinlich alles auf einmal verwendet, 2) es kann etwas mehr verwenden, abhängig von der Anzahl der eindeutigen oder doppelten Schlüssel.sort
auf temporäre Dateien zurück (auf intelligente Weise), um zu vermeiden, dass der Speicher voll wird . Die Speichernutzung ist gebunden. Die Grenze kann mit einigen Sortierimplementierungen angepasst werden. Es ist effizienter, wenn das System den Speicher zufällig auf die Festplatte austauscht (was sich auch auf Anwendungen auf dem System auswirkt).awk
stoßen, in dem der Arbeitsspeicher knapp wird, ist diessort
möglicherweise die einzige Lösung, da dieser entwickelt wurde, um dies zu beheben. Auf der anderen Seite wird das Lesen und Schreiben der Festplatte langsamer, sodass die Fertigstellung wahrscheinlich lange dauern wird. Wenn Sie mit so großen Datenmengen arbeiten, sollten Sie wahrscheinlich eher ein DBMS als Textdateien verwenden.O(n log n)
? Oder wissen Sie es einfach von woanders?Ich habe festgestellt, dass Sortieren das schnellste Uniq-Tool ist, wie hier gezeigt -> Schnellster Weg, um Duplikate in einer großen Wortliste zu löschen?
quelle
Ich wollte nur darauf hinweisen, dass Gnu
uniq
selbst auf einer sortierten Liste furchtbar langsam erscheint.Ich habe gerade versucht, eine Liste der Verzeichnispräfixe aus einer Liste sortierter Dateinamen abzurufen:
sort -u scheint doppelt so schnell wie uniq zu sein, und dies geschieht mit dem Lesen von stdin und dem Schreiben von stdout, sodass ich noch keine Parallelisierung sehe. Ich habe keine Ahnung, warum uniq so viel langsamer sein sollte als sortieren, da es die Liste nicht sortieren muss ...
Der Ausgang dieses Befehls ist sehr klein (es gibt viele Duplikate), nur 264 KB und die Sortierung wird sofort beendet, nachdem pv abgeschlossen ist.
Die gleichen Geschwindigkeiten bleiben erhalten, wenn Sie die Reihenfolge der Befehle ändern. Mein Fluss wird hier durch die CPU-Zeit begrenzt, nicht durch den Festplattenzugriff und die Caches (ich habe nur 8 GB RAM und mein Swap wird nicht verwendet).
Ich führe dies auf einer Fedora 31-Maschine mit gnu coreutils sort und uniq und gnu awk aus. Das Gebietsschema ist auf en_US.UTF-8 gesetzt
UPDATE , da mich das ziemlich fasziniert hat, habe ich noch einige Tests durchgeführt. Lassen Sie uns den ausgeschnittenen Teil aus dem Weg räumen und sicherstellen, dass die Datei gut sortiert ist
cat all_files | cut -d '/' -f 1,2,3,4 | sort -T . > test
Dies dauert 8,4 Minuten. Test ist jetzt 7,9 GB groß
Lassen Sie uns diese Tools in der Datei anstatt in einer Pipe ausführen. Dadurch können diese Tools noch weiter optimiert werden, z. B. sortieren wird mehrere Threads. und auch von einer schnelleren ssd.
Möglicherweise bemerken Sie nicht, dass das Sortieren auch viel Speicherplatz beansprucht, da es clevere Tricks mit temporären Dateien in / tmp ausführt, die möglicherweise tmpfs sind und sich in Ihrem RAM befinden. (Versuchen Sie, eine Datei zu sortieren, die größer als / tmp ist, und Sie werden in den Speicherplatz geraten Probleme, deshalb brauche ich das -T-Flag im obigen Befehl)
Es scheint also, dass Ihre awk-Lösung die schnellste von diesen 3 ist und tatsächlich den geringsten Speicher benötigt
Update2 und jetzt mit einem einfacheren Gebietsschema
Diesmal gewinnt uniq das Rennen ... wie Stéphane Chazelas in den Kommentaren andeutet, macht das Setzen Ihres Gebietsschemas auf C das Sortieren und uniq eine ganze Menge schneller!
quelle
sort
unduniq
? Welches Gebietsschema?