Schnellstes "Uniq" -Tool unter Linux

8

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 htopBefehl 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?

MLSC
quelle
Haben Sie versucht, sie auszuführen, möglicherweise mit time?
Choroba
Zeit ist wichtig und auch Speichernutzung und Zuverlässigkeit (ich meine,
wer
Noch nicht ... Aber ich habe vorher einige Tests gemacht ... und irgendwo gefragt, einige Leute haben mir gesagt, dass awk das Beste ist ... aber in htop ... ich sehe, dass die Speichernutzung zunimmt
MLSC
3
@ MortezaLSC: Es ist ein Kompromiss. Je schneller das Programm ist, desto mehr Speicher wird verwendet.
Cuonglm

Antworten:

16

Betrachten wir, wie jede Lösung funktioniert.

  • uniqDies setzt voraus, dass die Datei bereits sortiert ist. Wenn nicht, müssen Sie es sortzuerst sortdurchleiten , 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 von uniqist sehr billig, da nur benachbarte Zeilen seiner Eingabe verglichen werden müssen.

  • sort -uDies kombiniert die Arbeit von sort | uniq. Dies muss alle eindeutigen Eingaben im Speicher sammeln, wie es das awkSkript tut, aber es verschwendet auch Zeit, sie zu sortieren, bevor die Ausgabe erzeugt wird. Dies ist O(n log n), obwohl in diesem Fall ndie Anzahl der eindeutigen Elemente nicht alle Eingaben sind. Also ist es besser als die Pfeife.

  • sedIch bin mir nicht sicher, warum Sie dies aufgelistet haben, da ich mir überhaupt keinen guten Weg vorstellen kann, dies zu tun sed. Wenn Sie es zuerst sortieren und zu einem sedSkript weiterleiten, können Sie möglicherweise benachbarte Zeilen vergleichen. So sedwürde nur tun , was der uniqFall ist, und uniqwahrscheinlich tut es um so effizient wie möglich.

  • awkDies 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 verwendet O(n)Zeit und O(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.

Barmar
quelle
1
+1 Die Erklärung awkdazu 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.
Goldlöckchen
@Barmar Verzeihung, aber wenn ich eine große Datei (16 G) mit einer Speicherkapazität von 8 G habe, was wird dann mit meinem Speicher passieren?
MLSC
8
@goldilocks, greift sortauf 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).
Stéphane Chazelas
Das stimmt. Also, wenn Sie auf einen Fall stoßen, in demawk stoßen, in dem der Arbeitsspeicher knapp wird, ist dies sortmö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.
Barmar
@Barmar Wie haben Sie festgestellt, dass sich die Zeit für die Nachbestellung erhöht O(n log n)? Oder wissen Sie es einfach von woanders?
Jimmy
0

Ich wollte nur darauf hinweisen, dass Gnu uniqselbst auf einer sortierten Liste furchtbar langsam erscheint.

Ich habe gerade versucht, eine Liste der Verzeichnispräfixe aus einer Liste sortierter Dateinamen abzurufen:

$ pv all_files | cut -d '/' -f 1,2,3,4 | uniq > all_prefixes

36.7GiB 0:07:41 [81.4MiB/s]

$ pv all_files | cut -d '/' -f 1,2,3,4 | sort -u > all_prefixes2

36.7GiB 0:03:14 [ 193MiB/s]

$ pv all_files  | cut -d '/' -f 1,2,3,4 | awk '!x[$0]++' > all_prefixes3                                        
36.7GiB 0:02:18 [ 270MiB/s] 

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)

$ time sort -u test > /dev/null
339.24user 3.54system 1:28.87elapsed 385%CPU (0avgtext+0avgdata 2365856maxresident)k
9555544inputs+0outputs (0major+591298minor)pagefaults 0swaps

$ time awk '!x[$0]++' test > /dev/null                                                                                                                             
51.15user 1.55system 0:52.94elapsed 99%CPU (0avgtext+0avgdata 10976maxresident)k
0inputs+0outputs (0major+1923minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                  
421.89user 2.76system 7:06.63elapsed 99%CPU (0avgtext+0avgdata 1980maxresident)k
52712inputs+0outputs (0major+79minor)pagefaults 0swaps

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

$ export LC_ALL=c
$ time sort -u test > /dev/null                                                                                                                                             1.2m ? Tue Apr 21 17:09:22 2020
119.18user 3.64system 0:38.24elapsed 321%CPU (0avgtext+0avgdata 2013472maxresident)k

$ time awk '!x[$0]++' test > /dev/null                                                                                                                                1161ms ? Tue Apr 21 17:07:31 2020
67.23user 2.50system 1:10.16elapsed 99%CPU (0avgtext+0avgdata 10480maxresident)k
7187520inputs+0outputs (0major+1912minor)pagefaults 0swaps

$ time uniq test > /dev/null                                                                                                                                               
22.05user 2.02system 0:24.24elapsed 99%CPU (0avgtext+0avgdata 1488maxresident)k
2959648inputs+0outputs (1major+72minor)pagefaults 0swaps

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!

Jens Timmerman
quelle
Welche Implementierung von sortund uniq? Welches Gebietsschema?
Stéphane Chazelas