Warum ist max langsamer als sort?

Ich habe festgestellt, dass dies maxlangsamer ist als die sortFunktion in Python 2 und 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

Warum ist max ( O(n)) langsamer als die sortFunktion ( O(nlogn))?

Sie müssen sehr vorsichtig sein, wenn Sie das timeitModul in Python verwenden.

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

Hier wird der Initialisierungscode einmal ausgeführt, um ein zufälliges Array zu erstellen a. Dann wird der Rest des Codes mehrmals ausgeführt. Beim ersten Sortieren des Arrays, aber jedes zweite Mal, wenn Sie die Sortiermethode für ein bereits sortiertes Array aufrufen. Es wird nur die schnellste Zeit zurückgegeben, sodass Sie tatsächlich festlegen, wie lange Python benötigt, um ein bereits sortiertes Array zu sortieren.

Ein Teil des Sortieralgorithmus von Python besteht darin, zu erkennen, wann das Array bereits teilweise oder vollständig sortiert ist. Wenn es vollständig sortiert ist, muss es nur einmal das Array durchsuchen, um dies zu erkennen, und dann stoppt es.

Wenn Sie stattdessen versucht haben:

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

Dann erfolgt die Sortierung in jeder Zeitschleife und Sie können sehen, dass die Zeit zum Sortieren eines Arrays tatsächlich viel länger ist, als nur den Maximalwert zu finden.

Bearbeiten: Die Antwort von @ skyking erklärt den Teil, den ich ungeklärt gelassen habe: Er a.sort()weiß, dass er an einer Liste arbeitet, sodass er direkt auf die Elemente zugreifen kann. max(a)Funktioniert mit jeder beliebigen iterierbaren Datei und muss daher eine generische Iteration verwenden.

Beachten Sie zunächst, dass max()das Iterator-Protokoll verwendet wird , während list.sort()Ad-hoc-Code verwendet wird . Die Verwendung eines Iterators ist eindeutig ein wichtiger Aufwand. Deshalb beobachten Sie diesen zeitlichen Unterschied.

Abgesehen davon sind Ihre Tests jedoch nicht fair. Sie werden a.sort()mehrmals auf derselben Liste ausgeführt. Der von Python verwendete Algorithmus wurde speziell für schnelle (teilweise) sortierte Daten entwickelt. Ihre Tests zeigen, dass der Algorithmus seine Arbeit gut macht.

Dies sind faire Tests:

$ 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

Hier erstelle ich jedes Mal eine Kopie der Liste. Wie Sie sehen können, ist die Größenordnung der Ergebnisse unterschiedlich: Mikro- und Millisekunden, wie wir es erwarten würden.

Und denken Sie daran: big-Oh gibt eine Obergrenze an! Die Untergrenze für Pythons Sortieralgorithmus ist Ω ( n ). O ( n log n ) zu sein bedeutet nicht automatisch, dass jeder Lauf eine Zeit benötigt, die proportional zu n log n ist . Es bedeutet nicht einmal, dass es langsamer sein muss als ein O ( n ) -Algorithmus, aber das ist eine andere Geschichte. Es ist wichtig zu verstehen, dass in einigen günstigen Fällen ein O ( n log n ) -Algorithmus in O ( n ) -Zeit oder weniger ausgeführt werden kann.

Dies könnte daran liegen, dass l.sortein Mitglied von listwhile maxeine generische Funktion ist. Dies bedeutet, dass Sie l.sortsich auf die interne Darstellung von listwhile verlassen können und das maxgenerische Iteratorprotokoll durchlaufen müssen.

Dadurch ist jeder Elementabruf l.sortschneller als jeder Elementabruf max.

Ich gehe davon aus, dass Sie sorted(a)das Ergebnis langsamer als erhalten , wenn Sie stattdessen verwenden max(a).