Dlaczego Coreutils sortuje się wolniej niż Python?

Napisałem następujący skrypt, aby przetestować szybkość funkcji sortowania Pythona:

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

Następnie porównałem to do sortpolecenia coreutils w pliku zawierającym 10 milionów linii:

$ 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

Wbudowane polecenie wykorzystywało wszystkie cztery procesory (Python używał tylko jednego), ale jego uruchomienie zajęło około 3 razy! Co daje?

Używam Ubuntu 12.04.5 (32-bit), Python 2.7.3 i sort8.13

Komentarz Izkaty ujawnił odpowiedź: porównania specyficzne dla regionu. sortPolecenia używa ustawień wskazanego przez środowisko, podczas gdy domyślne Pythona w stosunku rzędu bajtów. Porównywanie ciągów UTF-8 jest trudniejsze niż porównywanie ciągów bajtów.

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

Co ty na to.

Jest to bardziej dodatkowa analiza niż faktyczna odpowiedź, ale wydaje się, że różni się w zależności od sortowanych danych. Po pierwsze, podstawowe czytanie:

$ 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 jest znacznie szybszy. Możesz jednak przyspieszyć coreutils sort, każąc mu sortować numerycznie:

$ 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

To jest znacznie szybsze, ale Python wciąż wygrywa z szerokim marginesem. Teraz spróbujmy jeszcze raz, ale z nieposortowaną listą liczb 1M:

$ 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

Coreutils sort -njest szybszy dla nieposortowanych danych liczbowych (chociaż możesz być w stanie ulepszyć cmpparametr sort python, aby przyspieszyć). Coreutils sortjest wciąż znacznie wolniejszy bez -nflagi. A co z losowymi znakami, a nie czystymi liczbami?

$ 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 wciąż bije coreutils, ale o wiele mniejszy margines niż to, co pokazujesz w swoim pytaniu. Zaskakujące jest to, że patrząc na czyste dane alfabetyczne jest jeszcze szybszy:

$ 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

Ważne jest również, aby pamiętać, że te dwa nie wytwarzają tego samego posortowanego wyjścia:

$ 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

Co dziwne, --buffer-sizeopcja ta nie zrobiła wiele (ani żadnej) różnicy w moich testach. Podsumowując, prawdopodobnie z powodu różnych algorytmów wymienionych w odpowiedzi goldilock, python sortwydaje się być szybszy w większości przypadków, ale GNU numerycznesort bije go na niesortowanych liczbach ¹ .

OP prawdopodobnie znalazł podstawową przyczynę, ale ze względu na kompletność, oto końcowe porównanie:

$ 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

¹ _{Ktoś z większą ilością python-fu niż powinienem spróbować przetestować poprawianie, list.sort()aby zobaczyć tę samą prędkość, można osiągnąć, określając metodę sortowania.}

Obie implementacje są w C, więc są tam równe szanse. Coreutils sort najwyraźniej wykorzystuje algorytm scalania . Mergesort wykonuje stałą liczbę porównań, które zwiększają się logarytmicznie do wielkości wejściowej, tj. Duże O (n log n).

Sortowanie w Pythonie używa unikalnego hybrydowego sortowania scalania / wstawiania, timsort , który wykona zmienną liczbę porównań z najlepszym scenariuszem O (n) - przypuszczalnie na już posortowanej liście - ale ogólnie jest logarytmiczny (logicznie, ty nie może być lepszy niż logarytmiczny w ogólnym przypadku podczas sortowania).

Biorąc pod uwagę dwa różne rodzaje logarytmiczne, jeden może mieć przewagę nad drugim w przypadku określonego zestawu danych. Tradycyjny sortowanie scalające nie zmienia się, więc będzie działał tak samo niezależnie od danych, ale np. Szybkie sortowanie (również logarytmiczne), które się zmienia, będzie działać lepiej na niektórych danych, a gorsze na innych.

Współczynnik trzy (lub więcej niż 3, ponieważ sortjest on zrównoleglony) jest dość spory, co sprawia, że ​​zastanawiam się, czy nie ma tu jakiejś nieprzewidzianej sytuacji, takiej jak sortzamiana na dysk ( -Topcja wydaje się sugerować, że tak jest). Jednak twój niski system vs. czas użytkownika sugeruje, że to nie jest problem.