Python sort() -Methode auf Liste vs eingebaute sorted() -Funktion

Question

Ich weiß, dass __builtin__ sortierte() Funktion auf jedem iterable funktioniert. Aber kann jemand diesen riesigen (10x) Leistungsunterschied zwischen anylist.sort() und sortierten (anylist) erklären? Bitte, weisen Sie auch darauf hin, wenn ich etwas falsch mache, wie dies gemessen wird.

 
""" 
Example Output: 
$ python list_sort_timeit.py 
Using sort method: 20.0662879944 
Using sorted builin method: 259.009809017 
""" 

import random 
import timeit 

print 'Using sort method:', 
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000)").repeat()) 
print x 

print 'Using sorted builin method:', 
x = min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000)").repeat()) 
print x 

---

Wie der Titel schon sagt, war ich interessiert List.Sort() vs sortiert (Liste) in den Vergleich. Das obige Snippet zeigte etwas Interessantes, dass sich die Sortierfunktion von Python sehr gut für bereits sortierte Daten verhält. Wie von Anurag aufgezeigt, arbeitet die Sortiermethode im ersten Fall an bereits sortierten Daten und während in der zweiten Sortierung arbeitet sie an neuen Stücken, um immer wieder zu arbeiten.

Also schrieb ich diese zu testen und ja, sie sind sehr nah.

 
""" 
Example Output: 
$ python list_sort_timeit.py 
Using sort method: 19.0166599751 
Using sorted builin method: 23.203567028 
""" 

import random 
import timeit 

print 'Using sort method:', 
x = min(timeit.Timer("test_list1.sort()","import random;test_list1=random.sample(xrange(1000),1000);test_list1.sort()").repeat()) 
print x 

print 'Using sorted builin method:', 
x = min(timeit.Timer("sorted(test_list2)","import random;test_list2=random.sample(xrange(1000),1000);test_list2.sort()").repeat()) 
print x 

Oh, sehe ich Alex Martelli mit einer Antwort, wie ich dies tippt .. (Ich werde die bearbeiten lassen, wie es sinnvoll sein könnte).

Answer 1

Ihre Fehler bei der Messung ist wie folgt: nach dem ersten Aufruf von test_list1.sort(), dass Liste Objekt IS sortiert - und Pythons Sortierung, aka timsort, ist sündig schnell auf bereits sortierten Listen !!! Das ist der häufigste Fehler bei der Verwendung von timeit - unbeabsichtigte Nebenwirkungen und nicht für sie.

Hier ist ein guter Satz von Messungen, timeit aus dem Zeilenbefehl wie es am besten verwendet wird:

$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' ' 
y=list(x); y.sort()' 
1000 loops, best of 3: 452 usec per loop 
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' ' 
x.sort()' 
10000 loops, best of 3: 37.4 usec per loop 
$ python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' ' 
sorted(x)' 
1000 loops, best of 3: 462 usec per loop 

Wie Sie sehen, y.sort() und sorted(x) sind Hals und Nacken, aber x.sort() dank der Gewinne Nebenwirkungen über der Vorteil einer Größenordnung - nur wegen Ihrer Messfehler, aber: das sagt Ihnen nichts über sort vs sorted per se!-)

Answer 2

Nun, die .sort() Methode der Listen sortiert die Liste an Ort und Stelle, während sorted() eine neue Liste erstellt. Wenn Sie also eine große Liste haben, ist ein Teil Ihrer Leistungsdifferenz auf das Kopieren zurückzuführen.

Noch scheint eine Größenordnung Unterschied größer als ich erwarten würde. Vielleicht hat list.sort() einige spezielle Gehäuse-Optimierung, die sorted() kann nicht nutzen. Da beispielsweise die Klasse list bereits über ein internes Py_Object*[]-Array mit der richtigen Größe verfügt, können Swaps möglicherweise effizienter ausgeführt werden.

Bearbeiten: Alex und Anurag haben Recht, die Größenordnung liegt daran, dass Sie versehentlich eine bereits sortierte Liste in Ihrem Testfall sortiert haben. Wie Alex 'Benchmarks zeigen, ist list.sort() jedoch etwa 2% schneller als sorted(), was aufgrund des Kopieraufwands sinnvoll wäre.

Answer 3

Weil list.sort an der richtigen Stelle sortiert, also zum ersten Mal sortiert, aber das nächste Mal sortieren Sie die sortierte Liste.

z.B. versuchen Sie dies und Sie werden dieselben Ergebnisse in timeit Fall die meiste Zeit verbracht wird kopiert und sortiert tut auch noch eine Kopie

import time 
import random 
test_list1=random.sample(xrange(1000),1000) 
test_list2=random.sample(xrange(1000),1000) 

s=time.time() 
for i in range(100): 
    test_list1.sort() 
print time.time()-s 

s=time.time() 
for i in range(100): 
    test_list2=sorted(test_list2) 
print time.time()-s