Perché il massimo è più lento di ordinare?

Question

Ho scoperto che max è più lento rispetto alla funzione sort in Python 2 e 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 

Perché èmax (O(n)) più lento della funzione sort (O(nlogn))?

Answer 1

È necessario prestare molta attenzione quando si utilizza il modulo timeit in Python.

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

Ecco il codice di inizializzazione viene eseguito una volta per produrre un allineamento randomizzato a. Quindi il resto del codice viene eseguito più volte. La prima volta ordina la matrice, ma ogni volta si chiama il metodo di ordinamento su una matrice già ordinata. Viene restituito solo il tempo più veloce, quindi in effetti è tempo di quanto tempo impiega Python per ordinare un array già ordinato.

Parte dell'algoritmo di ordinamento di Python è quello di rilevare quando l'array è già parzialmente o completamente ordinato. Quando è completamente ordinato, deve semplicemente effettuare una scansione una volta attraverso l'array per rilevare questo e poi si ferma.

Se invece provato:

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

poi il genere accade su ogni ciclo di temporizzazione e si può vedere che il tempo per ordinare un array è infatti molto più lungo rispetto al solo trovare il valore massimo.

Edit: @ di answer Skyking spiega la parte ho lasciato inspiegabile: a.sort() sa che sta lavorando su una lista in modo da può accedere direttamente agli elementi. max(a) funziona su qualsiasi iterabile arbitrario, quindi deve utilizzare l'iterazione generica.

Answer 2

Questo potrebbe essere dovuto al fatto che l.sort è un membro di list mentre max è una funzione generica. Ciò significa che l.sort può fare affidamento sulla rappresentazione interna di list mentre il max dovrà passare attraverso il protocollo iteratore generico.

Ciò rende ogni elemento recuperabile per l.sort più veloce di ogni elemento recuperato da max.

Suppongo che se si utilizza invece sorted(a) si otterrà il risultato più lentamente di max(a).

Answer 3

Prima di tutto, notare che max() uses the iterator protocol, mentre list.sort() uses ad-hoc code. Chiaramente, usare un iteratore è un overhead importante, ecco perché stai osservando questa differenza nei tempi.

Tuttavia, a parte questo, i test non sono equi. Stai eseguendo a.sort() nella stessa lista più di una volta. Lo algorithm used by Python è progettato specificamente per essere veloce per dati già ordinati (parzialmente). I tuoi test stanno dicendo che l'algoritmo sta facendo bene il suo lavoro.

Queste sono le prove equi:

$ 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 

Qui Sto creando una copia della lista ogni volta. Come puoi vedere, l'ordine di grandezza dei risultati è diverso: micro- vs millisecondi, come ci aspetteremmo.

E ricorda: big-Oh specifica un limite superiore! Il limite inferiore per l'algoritmo di ordinamento di Python è Ω (n). O Essere (n registro n) non implica automaticamente che ogni corsa richiede un tempo proporzionale alla n registro n. Non implica nemmeno che debba essere più lento di un algoritmo O (n), ma questa è un'altra storia. Ciò che è importante capire è che in alcuni casi favorevoli, un algoritmo O (n n) può essere eseguito in tempo O (n) o meno.