Python: toma max N elementos de alguna lista
¿Hay alguna función que me devuelva los N elementos más altos de alguna lista?
Es decir, 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 fácil y eficiente de obtenerlos? (Excepto la obvia implementación canónica; además, no hay tales cosas que involucren ordenar toda la lista primero porque eso sería ineficiente en comparación con la canónica solución.)
4 answers
>>> import heapq, random
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100)))
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254]
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-11-18 14:26:41
La función de la biblioteca estándar que hace esto es heapq.nlargest
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-11-18 14:41:29
Comience con los primeros 10 de L, llame a eso X. Tenga en cuenta 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) de X e inserte L[i]. Es posible que necesite mantener X como una lista vinculada ordenada y hacer una inserción. Actualizar min (X).
Al final, tienes los 10 valores más grandes en X.
Sospecho que será O(kN) (donde k es 10 aquí) ya que la ordenación por inserción es lineal. Podría ser lo que utiliza gsl, así que si usted puede leer algunos C código:
Http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html
Probablemente algo en numpy que hace esto.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-11-18 14:11:09
Una solución bastante eficiente es una variación de quicksort donde la recursión se limita a la parte derecha del pivote hasta que la posición del punto de pivote es mayor que el número de elementos requeridos (con algunas condiciones adicionales para tratar con casos de bordes, por supuesto).
La biblioteca estándar tiene heapq.nlargest, como han señalado otros aquí.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-01-17 13:32:11