Schnellstes `uniq`-Tool unter Linux

Question 1

Lassen Sie uns überlegen, wie jede Lösung funktioniert.

uniqDies setzt voraus, dass die Datei bereits sortiert ist. Wenn nicht, müssen Sie sie zuerst durchpipen sort, was bedeutet, dass sortdie gesamte Datei in den Speicher gelesen, neu sortiert ( O(n log n)) und dann in die Pipe geschrieben werden muss. Die Arbeit von uniqist sehr einfach, da nur benachbarte Zeilen der Eingabe verglichen werden müssen.
sort -uDies kombiniert die Arbeit von sort | uniq. Dies muss alle eindeutigen Eingaben im Speicher sammeln, wie das awkSkript es tut, verschwendet dann aber auch Zeit damit, sie zu sortieren, bevor die Ausgabe erstellt wird. Dies ist O(n log n), obwohl in diesem Fall ndie Anzahl der eindeutigen Elemente und nicht alle Eingaben ist. Es ist also besser als die Pipe.
sedIch bin mir nicht sicher, warum Sie das aufgelistet haben, da mir überhaupt keine gute Möglichkeit einfällt, dies zu tun sed. Vielleicht sedgibt es eine Möglichkeit, benachbarte Zeilen zu vergleichen, wenn Sie es zuerst sortieren und an ein Skript weiterleiten. Sie sedwürden also einfach das tun, was uniqfunktioniert, und uniqes wahrscheinlich so effizient wie möglich machen.
awkDies ist wahrscheinlich die beste Methode, da dabei nur der minimale Arbeitsaufwand erforderlich ist. Beim Lesen jeder Zeile führt es eine effiziente Hash-Suche durch, um zu sehen, ob die Zeile bereits im Speicher vorhanden ist, und speichert nur die eindeutigen Zeilen als Hash-Schlüssel und einen Zähler als Wert. (Wenn die Zeile zuvor nicht vorhanden war, ist die Bedingung erfüllt, sodass die Zeile gedruckt wird. Andernfalls geschieht dies nicht.) Dies verbraucht O(n)Zeit und O(uniq n)Speicher.

Jede Methode verbraucht eine beträchtliche Menge an Speicher, entweder zum Sortieren der Eingabe oder zum Verfolgen, welche Eingaben gesehen wurden, damit Duplikate entfernt werden können.

Answer

Lassen Sie uns überlegen, wie jede Lösung funktioniert.

uniqDies setzt voraus, dass die Datei bereits sortiert ist. Wenn nicht, müssen Sie sie zuerst durchpipen sort, was bedeutet, dass sortdie gesamte Datei in den Speicher gelesen, neu sortiert ( O(n log n)) und dann in die Pipe geschrieben werden muss. Die Arbeit von uniqist sehr einfach, da nur benachbarte Zeilen der Eingabe verglichen werden müssen.
sort -uDies kombiniert die Arbeit von sort | uniq. Dies muss alle eindeutigen Eingaben im Speicher sammeln, wie das awkSkript es tut, verschwendet dann aber auch Zeit damit, sie zu sortieren, bevor die Ausgabe erstellt wird. Dies ist O(n log n), obwohl in diesem Fall ndie Anzahl der eindeutigen Elemente und nicht alle Eingaben ist. Es ist also besser als die Pipe.
sedIch bin mir nicht sicher, warum Sie das aufgelistet haben, da mir überhaupt keine gute Möglichkeit einfällt, dies zu tun sed. Vielleicht sedgibt es eine Möglichkeit, benachbarte Zeilen zu vergleichen, wenn Sie es zuerst sortieren und an ein Skript weiterleiten. Sie sedwürden also einfach das tun, was uniqfunktioniert, und uniqes wahrscheinlich so effizient wie möglich machen.
awkDies ist wahrscheinlich die beste Methode, da dabei nur der minimale Arbeitsaufwand erforderlich ist. Beim Lesen jeder Zeile führt es eine effiziente Hash-Suche durch, um zu sehen, ob die Zeile bereits im Speicher vorhanden ist, und speichert nur die eindeutigen Zeilen als Hash-Schlüssel und einen Zähler als Wert. (Wenn die Zeile zuvor nicht vorhanden war, ist die Bedingung erfüllt, sodass die Zeile gedruckt wird. Andernfalls geschieht dies nicht.) Dies verbraucht O(n)Zeit und O(uniq n)Speicher.

Jede Methode verbraucht eine beträchtliche Menge an Speicher, entweder zum Sortieren der Eingabe oder zum Verfolgen, welche Eingaben gesehen wurden, damit Duplikate entfernt werden können.

Question 2

Ich wollte nur darauf hinweisen, dass GNU uniqselbst bei einer sortierten Liste furchtbar langsam zu sein scheint.

Ich habe gerade versucht, aus einer Liste sortierter Dateinamen eine Liste mit Verzeichnispräfixen 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 das mit sort, das von stdin liest und in stdout schreibt, also sehe ich noch keine Parallelisierung. Ich habe keine Ahnung, warum uniq so viel langsamer sein sollte als sort, da es die Liste nicht sortieren muss ...

Die Ausgabe dieses Befehls ist sehr klein (es gibt viele Duplikate), nur 264 KB, und das Sortieren wird sofort beendet, nachdem pv abgeschlossen ist.

Die Geschwindigkeit bleibt gleich, wenn Sie die Reihenfolge der Befehle umdrehen. Mein Datenfluss wird hier durch die CPU-Zeit begrenzt, nicht durch Festplattenzugriff und 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 eingestellt.

AKTUALISIEREN, da mich das ziemlich fasziniert hat, habe ich noch ein paar Tests gemacht, lasst 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. Der Test ist jetzt 7,9 GB groß

Lassen Sie uns diese Tools auf der Datei statt in einer Pipe ausführen. Dadurch können diese Tools weitere Optimierungen durchführen, z. B. das Sortieren mit mehreren Threads und auch von einer schnelleren SSD aus.

Ihnen fällt vielleicht nicht auf, dass die Sortierung auch viel Speicher verbraucht, da sie clevere Tricks mit temporären Dateien in /tmp anwendet, die möglicherweise tmpfs sind und sich in Ihrem RAM befinden (versuchen Sie, eine Datei zu sortieren, die größer als /tmp ist, Sie werden auf Speicherplatzprobleme stoßen, deshalb brauche ich das Flag -T 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

So scheint esIhre awk-Lösung ist die schnellste dieser 3und verbraucht tatsächlich am wenigsten Speicher

Aktualisierung2 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

Diesmaluniq gewinnt das Rennen... wie Stéphane Chazelas in den Kommentaren andeutet, werden Sort und Uniq um einiges schneller, wenn Sie Ihr Gebietsschema auf C setzen!

Answer