Warum werden Coreutils langsamer sortiert als Python?

20

Ich habe das folgende Skript geschrieben, um die Geschwindigkeit der Sortierfunktion von Python zu testen:

from sys import stdin, stdout
lines = list(stdin)
lines.sort()
stdout.writelines(lines)

Ich habe dies dann mit dem sortBefehl coreutils in einer Datei mit 10 Millionen Zeilen verglichen :

$ time python sort.py <numbers.txt >s1.txt
real    0m16.707s
user    0m16.288s
sys     0m0.420s

$ time sort <numbers.txt >s2.txt 
real    0m45.141s
user    2m28.304s
sys     0m0.380s

Der eingebaute Befehl verwendete alle vier CPUs (Python verwendete nur eine), dauerte jedoch ungefähr dreimal so lange! Was gibt?

Ich bin mit Ubuntu 12.04.5 (32-bit), Python 2.7.3 und sort8.13

augurar
quelle
@goldilocks Ja, schauen Sie sich den Benutzer in Echtzeit an.
24.
Huh - du hast recht. Anscheinend wurde es in Coreutils 8.6 parallelisiert.
Goldlöckchen
Können Sie --buffer-sizeangeben, dass der sortgesamte verfügbare physische Speicher verwendet wird, und prüfen, ob dies hilfreich ist?
Iruvar
@ 1_CR Versuchte es mit 1 GB Puffer, keine wesentliche Änderung im Timing. Davon wurden nur etwa 0,6 GB verwendet, sodass eine weitere Vergrößerung des Puffers nicht hilfreich wäre.
24.

Antworten:

22

Izkatas Kommentar ergab die Antwort: länderspezifische Vergleiche. Der sortBefehl verwendet das von der Umgebung angegebene Gebietsschema, während Python standardmäßig einen Vergleich der Byte-Reihenfolge vornimmt. Der Vergleich von UTF-8-Strings ist schwieriger als der Vergleich von Byte-Strings.

$ time (LC_ALL=C sort <numbers.txt >s2.txt)
real    0m5.485s
user    0m14.028s
sys     0m0.404s

Wie ist es damit.

augurar
quelle
Und wie vergleichen sie UTF-8-Zeichenfolgen?
Gilles 'SO- hör auf böse zu sein'
@Gilles Beim Ändern des Python-Skripts zum locale.strxfrmSortieren dauerte das Skript ~ 32 Sekunden, immer noch schneller als, sortaber viel weniger.
24.
3
Python 2.7.3 führt einen Byte-Vergleich durch, Python3 würde jedoch einen Unicode-Wortvergleich durchführen. Python3.3 ist für diesen "Test" etwa doppelt so langsam wie Python2.7. Der Aufwand für das Packen der unformatierten Bytes in die Unicode-Darstellung ist sogar höher als bei den bereits wichtigen Packobjekten, die Python 2.7.3 ausführen muss.
Anthon
2
Ich fand die gleiche Verlangsamung bei cutund auch bei anderen. Auf mehreren Maschinen habe ich jetzt export LC_ALL=Cin .bashrc. Aber Vorsicht: Dies bricht im Wesentlichen wc(außer wc -l), um nur ein Beispiel zu nennen. "Bad Bytes" werden überhaupt nicht gezählt ...
Walter Tross
1
Dieses Leistungsproblem tritt auch auf bei grep: Durch Deaktivieren von UTF-8 können Sie beim Greifen großer Dateien eine erhebliche Leistungsverbesserung erzielen, insbesondere dann, wenngrep -i
Adrian Pronk,
7

Dies ist eher eine zusätzliche Analyse als eine tatsächliche Antwort, scheint jedoch in Abhängigkeit von den zu sortierenden Daten zu variieren. Zunächst eine Basislesung:

$ printf "%s\n" {1..1000000} > numbers.txt

$ time python sort.py <numbers.txt >s1.txt
real    0m0.521s
user    0m0.216s
sys     0m0.100s

$ time sort <numbers.txt >s2.txt
real    0m3.708s
user    0m4.908s
sys     0m0.156s

OK, Python ist viel schneller. Sie können coreutils jedoch sortschneller machen, indem Sie ihm sagen, dass er numerisch sortieren soll:

$ time sort <numbers.txt >s2.txt 
real    0m3.743s
user    0m4.964s
sys     0m0.148s

$ time sort -n <numbers.txt >s2.txt 
real    0m0.733s
user    0m0.836s
sys     0m0.100s

Das ist viel schneller, aber Python gewinnt immer noch mit großem Abstand. Versuchen wir es jetzt noch einmal, aber mit einer nicht sortierten Liste von 1 Million Zahlen:

$ sort -R numbers.txt > randomized.txt

$ time sort -n <randomized.txt >s2.txt 
real    0m1.493s
user    0m1.920s
sys     0m0.116s

$ time python sort.py <randomized.txt >s1.txt
real    0m2.652s
user    0m1.988s
sys     0m0.064s

Die Funktion coreutils sort -nist schneller für unsortierte numerische Daten (obwohl Sie möglicherweise den cmpParameter der Python-Sortierung optimieren können , um sie schneller zu machen). Coreutils sortist ohne -nFlagge noch deutlich langsamer . Also, was ist mit zufälligen Zeichen, nicht reinen Zahlen?

$ tr -dc 'A-Za-z0-9' </dev/urandom | head -c1000000 | 
    sed 's/./&\n/g' > random.txt

$ time sort  <random.txt >s2.txt 
real    0m2.487s
user    0m3.480s
sys     0m0.128s

$ time python sort.py  <random.txt >s2.txt 
real    0m1.314s
user    0m0.744s
sys     0m0.068s

Python schlägt Coreutils immer noch, aber mit einem viel geringeren Abstand als das, was Sie in Ihrer Frage zeigen. Überraschenderweise ist es bei reinen alphabetischen Daten immer noch schneller:

$ tr -dc 'A-Za-z' </dev/urandom | head -c1000000 |
    sed 's/./&\n/g' > letters.txt

$ time sort   <letters.txt >s2.txt 
real    0m2.561s
user    0m3.684s
sys     0m0.100s

$ time python sort.py <letters.txt >s1.txt
real    0m1.297s
user    0m0.744s
sys     0m0.064s

Es ist auch wichtig zu beachten, dass die beiden nicht die gleiche sortierte Ausgabe erzeugen:

$ echo -e "A\nB\na\nb\n-" | sort -n
-
a
A
b
B

$ echo -e "A\nB\na\nb\n-" | python sort.py 
-
A
B
a
b

Seltsamerweise --buffer-sizeschien die Option bei meinen Tests keinen großen (oder keinen) Unterschied zu machen. Vermutlich aufgrund der verschiedenen Algorithmen, die in Goldilocks Antwort erwähnt wurden, sortscheint Python in den meisten Fällen schneller zu sein, aber numerische GNU sortschlägt es mit unsortierten Zahlen 1 .


Das OP hat wahrscheinlich die Ursache gefunden, aber der Vollständigkeit halber hier ein letzter Vergleich:

$ time LC_ALL=C sort   <letters.txt >s2.txt 
real    0m0.280s
user    0m0.512s
sys     0m0.084s


$ time LC_ALL=C python sort.py   <letters.txt >s2.txt 
real    0m0.493s
user    0m0.448s
sys     0m0.044s

1 Jemand mit mehr Python-Fu, als ich versuchen sollte, das Tweaken zu testen list.sort(), um die gleiche Geschwindigkeit zu erzielen, kann durch Angabe der Sortiermethode erreicht werden.

terdon
quelle
5
Python-Sortierung hat einen zusätzlichen Geschwindigkeitsvorteil, basierend auf Ihrem letzten Beispiel: Numerische ASCII-Reihenfolge. sortscheint ein wenig zusätzliche Arbeit für Vergleiche zwischen Groß- und Kleinschreibung zu leisten.
Izkata
@Izkata Das war's! Siehe meine Antwort unten.
24.
1
Tatsächlich hat Python einen erheblichen Overhead, da seine internen Zeichenfolgen aus den Rohdaten erstellt stdinwerden. Konvertieren von denen in Zahlen ( lines = map(int, list(stdin))) und zurück ( stdout.writelines(map(str,lines))) macht die ganze Sortierung langsamer gehen, bis von 0.234s real 0.720s auf meinem Rechner.
Anthon
6

Beide Implementierungen befinden sich in C, was dort zu gleichen Wettbewerbsbedingungen führt. Coreutils verwendet sort offenbar den Mergesort- Algorithmus. Mergesort führt eine feste Anzahl von Vergleichen durch, die logarithmisch mit der Eingabegröße zunimmt, dh groß O (n log n).

Pythons Sortierung verwendet eine eindeutige hybride Sortierung für Zusammenführung / Einfügung, timsort , die eine variable Anzahl von Vergleichen mit einem Best-Case-Szenario von O (n) ausführt - vermutlich auf einer bereits sortierten Liste -, aber im Allgemeinen logarithmisch ist (logischerweise Sie) kann nicht besser als logarithmisch für den allgemeinen Fall beim Sortieren werden).

Bei zwei verschiedenen logarithmischen Sortierungen könnte eine in einem bestimmten Datensatz einen Vorteil gegenüber der anderen haben. Eine herkömmliche Zusammenführungssortierung ändert sich nicht, so dass sie unabhängig von den Daten dieselbe Leistung erbringt, aber z. B. variiert die Quicksortierung (auch logarithmisch) bei einigen Daten besser, bei anderen jedoch schlechter.

Ein Faktor von drei (oder mehr als drei, da sortparallelisiert) ist jedoch ziemlich viel, was mich fragt, ob es hier keine Kontingenz gibt, wie beispielsweise das sortWechseln auf eine Festplatte (die -TOption scheint dies zu implizieren). Aufgrund Ihrer geringen System- und Benutzerzeit ist dies jedoch nicht das Problem.

Goldlöckchen
quelle
Guter Punkt, dass beide Implementierungen in C geschrieben sind. Ich bin mir sicher, wenn ich einen Sortieralgorithmus in Python implementieren würde, wäre er viel, viel langsamer.
24.
Übrigens besteht die Datei aus zufällig generierten Gleitkommawerten zwischen 0 und 1, sodass nicht zu viel Struktur zum Ausnutzen vorhanden sein sollte.
24.