Dlaczego Coreutils sortuje się wolniej niż Python?

20

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

augurar
źródło
@Goldilocks Tak, spójrz na użytkownika w czasie rzeczywistym.
sierpień
Huh - masz rację. Najwyraźniej została zrównoleglona w Coreutils 8.6.
goldilocks
Czy możesz użyć, --buffer-sizeaby określić sortużycie całej dostępnej pamięci fizycznej i sprawdzić, czy to pomaga?
iruvar
@ 1_CR Próbowałem z 1 GB buforem, bez znaczących zmian w taktowaniu. Zużyło to tylko około .6 GB, więc dalsze zwiększenie rozmiaru bufora nie pomogłoby.
sierpień

Odpowiedzi:

22

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.

augurar
źródło
Jak porównują ciągi UTF-8?
Gilles „SO- przestań być zły”
@Gilles Modyfikując skrypt Pythona locale.strxfrmdo sortowania, skrypt zajął ~ 32 sekundy, wciąż szybciej niż, sortale znacznie mniej.
sierpień
3
Python 2.7.3 dokonuje porównania bajtów, ale Python3 porównałby słowa Unicode. Python3.3 jest około dwa razy wolniejszy dla tego „testu”. Narzut związany z pakowaniem nieprzetworzonych bajtów do reprezentacji Unicode jest nawet większy niż znaczące już obiekty do pakowania, które musi wykonać Python 2.7.3.
Anthon
2
Znalazłem to samo spowolnienie z cuti innymi. Na kilku maszynach Mam teraz export LC_ALL=Cw .bashrc. Ale uwaga: to zasadniczo psuje się wc(z wyjątkiem wc -l), żeby wymienić tylko przykład. „Złe bajty” w ogóle się nie liczą ...
Walter Tross
1
Ten problem z wydajnością występuje również w przypadku grep: można uzyskać znaczną poprawę wydajności podczas grepowania dużych plików poprzez wyłączenie UTF-8, szczególnie podczas wykonywaniagrep -i
Adrian Pronk
7

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 1 .


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

1 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.

terdon
źródło
5
Sortowanie w języku Python ma dodatkową przewagę szybkości, w oparciu o ostatnią próbkę: porządek numeryczny ASCII. sortwydaje się, że wykonuje trochę dodatkowej pracy dla porównań wielkich i małych liter.
Izkata
@Izkata To wszystko! Zobacz moją odpowiedź poniżej.
sierpień
1
W rzeczywistości python ma sporo narzutu, tworząc swoje wewnętrzne ciągi z surowego stdinwejścia. Konwersja do tych numerów ( lines = map(int, list(stdin))) iz powrotem ( stdout.writelines(map(str,lines))) sprawia, że cały sortowania iść wolniej, od 0.234s realne 0.720s na moim komputerze.
Anthon
6

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.

Złotowłosa
źródło
Dobrze, że obie implementacje są napisane w C. Jestem pewien, że jeśli zaimplementuję algorytm sortowania w Pythonie, byłoby to znacznie, dużo wolniejsze.
sierpień
Nawiasem mówiąc, plik składa się z losowo generowanych wartości zmiennoprzecinkowych od 0 do 1, więc nie powinno być zbyt wiele struktur do wykorzystania.
sierpień