Python: tome elementos N máximos de alguna lista

Question

¿Hay alguna función que me devolvería los N elementos más altos de alguna lista?

I.e. si max(l) devuelve el elemento más alto, sth. como max(l, count=10) me devolvería una lista de los 10 números más altos (o menos si l es más pequeño).

¿O cuál sería una manera eficiente y fácil de conseguir esto? (Excepto la implementación canónica obvia; tampoco hay cosas que impliquen clasificar toda la lista primero porque sería ineficiente en comparación con la solución canónica).

Answer 1

heapq.nlargest:

>>> import heapq, random 
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100))) 
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254] 

Answer 2

Una solución bastante eficiente es una variación de quicksort donde la recursión se limita al parte derecha del pivote hasta que la posición del punto de pivote sea más alta que la cantidad de elementos requeridos (con algunas condiciones adicionales para tratar los casos de borde, por supuesto).

La biblioteca estándar tiene heapq.nlargest, como señalaron otros aquí.

Answer 3

de inicio con el primer 10 a partir de L, que llame X. Nota el valor mínimo de X.

bucle sobre L [i] para i sobre el resto de L.

Si L [i] es mayor que min (X), suelte min (X) desde X e inserte L [i]. Es posible que deba mantener X como una lista enlazada ordenada y hacer una inserción. Actualizar min (X).

Al final, usted tiene los 10 valores más grandes de X.

sospecho que va a ser O (kN) (donde k es 10 aquí) ya la ordenación por inserción es lineal. Podría ser lo utiliza GSL, por lo que si se puede leer algo de código C:

http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html

Probablemente algo en numpy que hace esto.

Answer 4

La función de la biblioteca estándar que tiene esto es heapq.nlargest