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 sort
polecenia 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 sort
8.13
--buffer-size
aby określićsort
użycie całej dostępnej pamięci fizycznej i sprawdzić, czy to pomaga?Odpowiedzi:
Komentarz Izkaty ujawnił odpowiedź: porównania specyficzne dla regionu.
sort
Polecenia 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.Co ty na to.
źródło
locale.strxfrm
do sortowania, skrypt zajął ~ 32 sekundy, wciąż szybciej niż,sort
ale znacznie mniej.cut
i innymi. Na kilku maszynach Mam terazexport LC_ALL=C
w.bashrc
. Ale uwaga: to zasadniczo psuje sięwc
(z wyjątkiemwc -l
), żeby wymienić tylko przykład. „Złe bajty” w ogóle się nie liczą ...grep
: można uzyskać znaczną poprawę wydajności podczas grepowania dużych plików poprzez wyłączenie UTF-8, szczególnie podczas wykonywaniagrep -i
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:
OK, python jest znacznie szybszy. Możesz jednak przyspieszyć coreutils
sort
, każąc mu sortować numerycznie:To jest znacznie szybsze, ale Python wciąż wygrywa z szerokim marginesem. Teraz spróbujmy jeszcze raz, ale z nieposortowaną listą liczb 1M:
Coreutils
sort -n
jest szybszy dla nieposortowanych danych liczbowych (chociaż możesz być w stanie ulepszyćcmp
parametr sort python, aby przyspieszyć). Coreutilssort
jest wciąż znacznie wolniejszy bez-n
flagi. A co z losowymi znakami, a nie czystymi liczbami?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:
Ważne jest również, aby pamiętać, że te dwa nie wytwarzają tego samego posortowanego wyjścia:
Co dziwne,
--buffer-size
opcja 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, pythonsort
wydaje 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:
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.źródło
sort
wydaje się, że wykonuje trochę dodatkowej pracy dla porównań wielkich i małych liter.stdin
wejś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, aż od 0.234s realne 0.720s na moim komputerze.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ż
sort
jest on zrównoleglony) jest dość spory, co sprawia, że zastanawiam się, czy nie ma tu jakiejś nieprzewidzianej sytuacji, takiej jaksort
zamiana na dysk (-T
opcja wydaje się sugerować, że tak jest). Jednak twój niski system vs. czas użytkownika sugeruje, że to nie jest problem.źródło