Dlaczego max działa wolniej niż sort?

Odkryłem, że maxjest wolniejszy niż sortfunkcja w Pythonie 2 i 3.

Python 2

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'        
1000 loops, best of 3: 342 usec per loop

Python 3

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop

Dlaczego jest max ( O(n)) wolniej niż sortfunkcja ( O(nlogn))?

Musisz być bardzo ostrożny używając timeitmodułu w Pythonie.

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'

Tutaj kod inicjalizacyjny jest uruchamiany raz, aby utworzyć losową tablicę a. Następnie reszta kodu jest uruchamiana kilka razy. Za pierwszym razem sortuje tablicę, ale za każdym razem, gdy wywołujesz metodę sort na już posortowanej tablicy. Zwracany jest tylko najszybszy czas, więc tak naprawdę odliczasz, ile czasu zajmie Pythonowi posortowanie już posortowanej tablicy.

Częścią algorytmu sortowania Pythona jest wykrywanie, kiedy tablica jest już częściowo lub całkowicie posortowana. Po całkowitym posortowaniu musi po prostu raz przeskanować macierz, aby to wykryć, a następnie zatrzymuje się.

Jeśli zamiast tego próbowałeś:

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'

wtedy sortowanie odbywa się w każdej pętli czasowej i widać, że czas na sortowanie tablicy jest rzeczywiście znacznie dłuższy niż znalezienie maksymalnej wartości.

Edit: @ skyking na odpowiedź wyjaśnia część zostawiłem niewyjaśnione: a.sort()wie, że pracuje na liście, więc można bezpośrednio uzyskać dostęp do elementów. max(a)działa na dowolnej dowolnej iteracji, więc musi używać ogólnej iteracji.

Po pierwsze, należy zauważyć, że max()używa protokołu iteratora , podczas gdy list.sort()używa kodu ad-hoc . Oczywiście używanie iteratora jest ważnym narzutem, dlatego obserwujesz tę różnicę w czasie.

Jednak poza tym twoje testy nie są sprawiedliwe. Jesteś a.sort()na tej samej liście więcej niż raz. Algorytm Python jest zaprojektowana jako szybka już (częściowo) posortowane dane. Twoje testy wskazują, że algorytm dobrze wykonuje swoją pracę.

To są uczciwe testy:

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a[:])'
1000 loops, best of 3: 227 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a[:].sort()'
100 loops, best of 3: 2.28 msec per loop

Tutaj za każdym razem tworzę kopię listy. Jak widać, rząd wielkości wyników jest inny: mikro- vs milisekundy, tak jak byśmy się spodziewali.

I pamiętaj: big-Oh określa górną granicę! Dolna granica algorytmu sortowania Pythona to Ω ( n ). Bycie O ( n log n ) nie oznacza automatycznie, że każdy przebieg zajmuje czas proporcjonalny do n log n . Nie oznacza to nawet, że musi być wolniejszy niż algorytm O ( n ), ale to już inna historia. Ważne jest, aby zrozumieć, że w niektórych korzystnych przypadkach algorytm O ( n log n ) może działać w czasie O ( n ) lub krótszym.

Może to być spowodowane tym, że l.sortelement członkowski listwhile maxjest funkcją ogólną. Oznacza to, że l.sortmoże polegać na wewnętrznej reprezentacji listwhile maxbędzie musiał przejść przez ogólny protokół iteratora.

To sprawia, że ​​każdy element pobiera l.sortszybciej niż każdy element, który to maxrobi.

Zakładam, że jeśli zamiast tego użyjesz sorted(a), uzyskasz wynik wolniej niż max(a).