forma más eficiente de encontrar el flotador mínimo de una lista de pitón

Question

Una pregunta rápida, lo que es más eficiente para encontrar el número más pequeño (float) en una larga lista (10000 + elementos)

es que

min(mylist) 

o

mylist.sort() 

y luego regresar

mylist[0] 

o algo más ...

gracias!

Answer 1

Si la lista ya está completa, min() es la forma más eficiente.

Hay algunos trucos que puedes usar en escenarios especiales:

• Si se construye la lista desde cero, simplemente mantener el elemento más pequeño sin embargo, en una variable externa, por lo que la respuesta será dada en O(1).
• Si solo hay flotadores en la lista, use un Array que le da un mejor rendimiento.
• Puede mantener la lista ordenada usando bisect.
• Utilice un Python Heap, que incluso tiene una implementación eficiente de min(). Asegúrese de comprender los efectos, principalmente una inserción más lenta. (credit: interjay)

Answer 2

Bueno, definitivamente tiene que iterar sobre toda la lista, por lo que su tiempo de ejecución debe ser O (n).

Como una ordenación ya lleva tiempo O (n log n), obviamente esta no es la mejor manera de hacerlo. No sé la implementación de min(), pero debería ser la forma correcta de hacerlo.

Answer 3

Frst, si se preocupan por el rendimiento en Python (que no siempre es una cosa sensible a preocuparse, pero eso es otra conversación), usted debe utilizar el timeit module. Incluso en C es difícil predecir cómo se comportarán ciertas funciones después de la compilación, y es más difícil en Python. Con frecuencia, las personas expresan con confianza opiniones sobre qué funciones son más rápidas y cuáles dependen de los datos. Entonces, al usar timeit, quiero decir, podrías haberlo descubierto tú mismo.

En segundo lugar, si realmente se preocupan por el rendimiento en las listas de flotadores, no debe usar listas en absoluto, sino matrices numpy. Usando IPython aquí, en Python 2.7.2, lo que hace que el tiempo sea más fácil:

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 

Y observamos algunas cosas. (1) El género de Python (timsort) funciona muy bien en los datos que tienen corridas ordenadas, por lo que ordenar una lista ya ordenada casi no tiene penalización. (2) La clasificación de una lista aleatoria, por otro lado, es mucho más lenta, y esto solo empeorará a medida que los datos crezcan. (3) Numpy.min() en una matriz flotante funciona sesenta veces más rápido que min en una lista de Python, porque no tiene que ser tan general.