Perché la ricerca nell'elenco ordinato in python richiede più tempo?

Question

Ho fatto un esperimento in cui ho cercato di trovare il tempo necessario per cercare in una lista python. Ho una lista arr con numeri casuali. arr_s ha gli stessi elementi solo ordinati.

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

Ora creare un array casuale di numeri interi find che ha elementi che voglio cercare in arr e arr_s.

>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr: 
...:  continue 

[OUT]:100 loops, best of 3: 2.18 ms per loop 


>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr_s: 
...:  continue 

[OUT]:100 loops, best of 3: 5.15 ms per loop 

Adesso ho capito che non ho usato alcun metodo specifico per la ricerca nella matrice ordinata (ad esempio ricerca binaria). Quindi potrebbe fare la ricerca lineare standard, ma perché ci vuole molto più tempo per cercare nell'array ordinato che nella matrice non ordinata? Penserei che dovrebbe prendere quasi lo stesso tempo. Ho provato tutti i tipi di array find. Matrici che hanno numeri interi da (0, 1000), (-1000, -100) e (-10000, 10000) i cicli richiedono sempre più tempo per l'array ordinato.

Answer 1

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

arr è un array. arr_s è una lista. La ricerca di un array può essere gestita in modo efficiente da numpy, ma la ricerca in un elenco richiede i seguenti indicatori e l'esecuzione di controlli del tipo. Non ha nulla a che fare con l'ordinamento.

Nota: in does weird things in numpy. L'utilizzo di in con numdy ndarrays può essere una cattiva idea.

Answer 2

Gli elenchi Python non sono come gli array C. Non sono solo un semplice blocco di memoria in cui l'elemento 1 viene sempre dopo l'elemento 0 e così via. Invece, sotto il cofano, Python memorizza le cose in modo flessibile in modo da poter aggiungere e rimuovere elementi di tipi arbitrari e spostare le cose a volontà.

In questo caso, la mia ipotesi è che l'atto di ordinare l'elenco cambia l'organizzazione sottostante, rendendo un po 'meno efficiente per accedere agli elementi.

Answer 3

Non ho una risposta esatta ma un possibile punto di partenza è controllare gli iteratori utilizzati da ciascun oggetto.

    In [9]: it = arr.__iter__() 
    In [10]: its = arr_s.__iter__() 
    In [11]: type(it) 
    Out[11]: iterator 
    In [12]: type(its) 
    Out[12]: listiterator 

Apparentemente utilizzano due iteratori diversi che potrebbero spiegare la differenza di velocità.