modo più efficiente di trovare il flottante minimo in una lista python

Question

Domanda rapida, che è più efficiente per trovare il più piccolo numero (float) di una lunga lista (10000+ elementi)

è vero

min(mylist) 

o

mylist.sort() 

e poi tornare

mylist[0] 

o altro ...

grazie!

Answer 1

Se l'elenco è già compilato, min() è il modo più efficiente.

Ci sono alcuni trucchi che si potrebbe utilizzare in scenari speciali:

• Se si crea la lista da zero, semplicemente tenere l'elemento più piccolo ma in una variabile esterna, in modo che la risposta sarà data in O(1).
• Se nell'elenco è presente solo float, utilizzare uno Array che offre prestazioni migliori.
• È possibile mantenere ordinato l'elenco utilizzando bisect.
• Utilizzare uno Python Heap, che ha anche un'implementazione efficiente di min(). Assicurati di aver compreso gli effetti, principalmente un inserimento più lento. (credit: interjay)

Answer 2

Bene, devi assolutamente ripetere l'intera lista, quindi il tuo runtime dovrebbe essere O (n).

Come un ordinamento già richiede O (n log n), questo non è ovviamente il modo migliore per farlo. Non conosco l'implementazione di min(), ma dovrebbe essere il modo giusto per farlo.

Answer 3

Frst, se vi preoccupate per le prestazioni in Python (che non è sempre una cosa sensata da preoccuparsi, ma questa è un'altra conversazione), si dovrebbe utilizzare il timeit module. Anche in C è difficile prevedere in che modo determinate funzioni si comporteranno dopo la compilazione, ed è più difficile in Python. Le persone spesso esprimono con fiducia opinioni su quali funzioni sono più veloci e dipendenti dai dati. Quindi - usando timeit, intendo - potresti aver scoperto te stesso.

In secondo luogo, se si in realtà si preoccupano delle prestazioni negli elenchi di float, non si dovrebbero utilizzare elenchi, ma array numpy. Utilizzando IPython qui, sotto Python 2.7.2, che semplifica le cose:

In [41]: import random, numpy 
In [42]: a = [0.1*i for i in range(10**5)] 
In [43]: timeit min(a) 
100 loops, best of 3: 4.55 ms per loop 
In [44]: timeit sorted(a)[0] 
100 loops, best of 3: 4.57 ms per loop 
In [45]: random.shuffle(a) 
In [46]: timeit min(a) 
100 loops, best of 3: 6.06 ms per loop 
In [47]: timeit min(a) # to make sure it wasn't a fluke 
100 loops, best of 3: 6.07 ms per loop 
In [48]: timeit sorted(a)[0] 
10 loops, best of 3: 65.9 ms per loop 
In [49]: b = numpy.array(a) 
In [50]: timeit b.min() 
10000 loops, best of 3: 97.5 us per loop 

E notiamo alcune cose. (1) L'ordinamento di Python (timsort) funziona molto bene sui dati che hanno le esecuzioni ordinate, quindi l'ordinamento di una lista già ordinata non ha quasi nessuna penalità. (2) L'ordinamento di una lista casuale, d'altra parte, è molto più lento, e questo peggiorerà solo con l'aumentare dei dati. (3) Numpy.min() su un array float funziona sessanta volte più velocemente del min su un elenco Python, perché non deve essere come generale.