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 sort
Befehl 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 sort
8.13
--buffer-size
angeben, dass dersort
gesamte verfügbare physische Speicher verwendet wird, und prüfen, ob dies hilfreich ist?Antworten:
Izkatas Kommentar ergab die Antwort: länderspezifische Vergleiche. Der
sort
Befehl 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.Wie ist es damit.
quelle
locale.strxfrm
Sortieren dauerte das Skript ~ 32 Sekunden, immer noch schneller als,sort
aber viel weniger.cut
und auch bei anderen. Auf mehreren Maschinen habe ich jetztexport LC_ALL=C
in.bashrc
. Aber Vorsicht: Dies bricht im Wesentlichenwc
(außerwc -l
), um nur ein Beispiel zu nennen. "Bad Bytes" werden überhaupt nicht gezählt ...grep
: Durch Deaktivieren von UTF-8 können Sie beim Greifen großer Dateien eine erhebliche Leistungsverbesserung erzielen, insbesondere dann, wenngrep -i
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:
OK, Python ist viel schneller. Sie können coreutils jedoch
sort
schneller machen, indem Sie ihm sagen, dass er numerisch sortieren soll: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:
Die Funktion coreutils
sort -n
ist schneller für unsortierte numerische Daten (obwohl Sie möglicherweise dencmp
Parameter der Python-Sortierung optimieren können , um sie schneller zu machen). Coreutilssort
ist ohne-n
Flagge noch deutlich langsamer . Also, was ist mit zufälligen Zeichen, nicht reinen Zahlen?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:
Es ist auch wichtig zu beachten, dass die beiden nicht die gleiche sortierte Ausgabe erzeugen:
Seltsamerweise
--buffer-size
schien 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,sort
scheint Python in den meisten Fällen schneller zu sein, aber numerische GNUsort
schlägt es mit unsortierten Zahlen 1 .Das OP hat wahrscheinlich die Ursache gefunden, aber der Vollständigkeit halber hier ein letzter Vergleich:
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.quelle
sort
scheint ein wenig zusätzliche Arbeit für Vergleiche zwischen Groß- und Kleinschreibung zu leisten.stdin
werden. 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.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
sort
parallelisiert) ist jedoch ziemlich viel, was mich fragt, ob es hier keine Kontingenz gibt, wie beispielsweise dassort
Wechseln auf eine Festplatte (die-T
Option scheint dies zu implizieren). Aufgrund Ihrer geringen System- und Benutzerzeit ist dies jedoch nicht das Problem.quelle