Mengapa max lebih lambat dari sort?

Saya telah menemukan itu maxlebih lambat daripada sortfungsi di Python 2 dan 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

Mengapa adalah max ( O(n)) lebih lambat dibandingkan dengan sortfungsi ( O(nlogn))?

Anda harus sangat berhati-hati saat menggunakan timeitmodul dengan Python.

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

Di sini kode inisialisasi dijalankan sekali untuk menghasilkan larik acak a. Kemudian sisa kode dijalankan beberapa kali. Pertama kali ini mengurutkan larik, tetapi setiap kali Anda memanggil metode pengurutan pada larik yang sudah diurutkan. Hanya waktu tercepat yang dikembalikan, jadi Anda sebenarnya menghitung waktu berapa lama waktu yang dibutuhkan Python untuk mengurutkan array yang sudah diurutkan.

Bagian dari algoritma pengurutan Python adalah untuk mendeteksi ketika larik sudah sebagian atau seluruhnya diurutkan. Ketika benar-benar diurutkan, ia hanya perlu memindai sekali melalui array untuk mendeteksi ini dan kemudian berhenti.

Jika sebaliknya Anda mencoba:

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

kemudian pengurutan terjadi pada setiap putaran waktu dan Anda dapat melihat bahwa waktu untuk mengurutkan array memang jauh lebih lama daripada hanya menemukan nilai maksimum.

Edit: @ Skyking ini jawabannya menjelaskan bagian saya meninggalkan dijelaskan: a.sort()tahu itu bekerja pada daftar sehingga dapat langsung mengakses elemen. max(a)bekerja pada sembarang iterable sehingga harus menggunakan iterasi generik.

Pertama, perhatikan yang max()menggunakan protokol iterator , sementara list.sort()menggunakan kode ad-hoc . Jelas, menggunakan iterator adalah overhead yang penting, itulah mengapa Anda mengamati perbedaan waktu itu.

Namun, selain itu, pengujian Anda tidak adil. Anda menjalankan a.sort()daftar yang sama lebih dari sekali. The algoritma yang digunakan oleh Python secara khusus dirancang untuk menjadi cepat untuk sudah (sebagian) diurutkan data. Pengujian Anda menunjukkan bahwa algoritme tersebut melakukan tugasnya dengan baik.

Ini adalah tes yang adil:

$ 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

Di sini saya membuat salinan daftar setiap saat. Seperti yang Anda lihat, urutan besarnya hasil berbeda: mikro vs milidetik, seperti yang kita perkirakan.

Dan ingat: big-Oh menentukan batas atas! Batas bawah untuk algoritma pengurutan Python adalah Ω ( n ). Menjadi O ( n log n ) tidak secara otomatis menyiratkan bahwa setiap proses membutuhkan waktu yang sebanding dengan n log n . Ini bahkan tidak menyiratkan bahwa itu harus lebih lambat dari algoritma O ( n ), tapi itu cerita lain. Yang penting untuk dipahami adalah bahwa dalam beberapa kasus yang menguntungkan, algoritme O ( n log n ) dapat berjalan dalam waktu O ( n ) atau kurang.

Ini bisa jadi karena l.sortadalah anggota listwhile maxadalah fungsi generik. Ini berarti bahwa l.sortdapat mengandalkan representasi internal listsementara maxharus melalui protokol iterator generik.

Ini membuat setiap pengambilan elemen l.sortlebih cepat daripada setiap elemen yang diambil max.

Saya berasumsi bahwa jika Anda malah menggunakan sorted(a)Anda akan mendapatkan hasil lebih lambat dari max(a).