cómo obtener de manera eficiente los elementos k más grandes de una lista en python

Question

¿Cuál es la forma más eficiente, elegante y pitónica de resolver este problema?

Dada una lista (o conjunto o lo que sea) de n elementos, queremos obtener los k más grandes. (Se puede suponer k<n/2 sin pérdida de generalidad, supongo) Por ejemplo, si la lista fueron:

l = [9,1,6,4,2,8,3,7,5] 

n = 9, y digamos k = 3. ¿Cuál es el algoritmo más eficiente para la recuperación de la 3 los más grandes? En este caso deberíamos obtener [9,8,7], sin ningún orden en particular.

Gracias! Manuel

Answer 1

Uso nlargest del módulo heapq

from heapq import nlargest 
lst = [9,1,6,4,2,8,3,7,5] 
nlargest(3, lst) # Gives [9,8,7] 

También puede dar una clave para nlargest en caso de que quiere cambiar sus criterios:

from heapq import nlargest 
tags = [ ("python", 30), ("ruby", 25), ("c++", 50), ("lisp", 20) ] 
nlargest(2, tags, key=lambda e:e[1]) # Gives [ ("c++", 50), ("python", 30) ] 

Answer 2

l = [9,1,6,4,2,8,3,7,5] 

sorted(l)[-k:] 

Answer 3

Usted puede utilizar el módulo heapq .

>>> from heapq import heapify, nlargest 
>>> l = [9,1,6,4,2,8,3,7,5] 
>>> heapify(l) 
>>> nlargest(3, l) 
[9, 8, 7] 
>>> 

Answer 4

sorted(l, reverse=True)[:k] 

Answer 5

El simple, O (log n n) forma es para ordenar la lista a continuación, obtener los últimos k elementos.

La manera correcta es usar un selection algorithm, que se ejecuta en tiempo O (n + k log k).

También, heapq.nlargesttakes O(n log k) time, que puede o no ser lo suficientemente bueno.

(Si k = O (n), entonces los 3 algoritmos tienen la misma complejidad (es decir, no molestar). Si k = O (log n), el algoritmo de selección descrito en Wikipedia es O (n) y heapq.nlargest es O (n log log n), pero el logaritmo doble es "lo suficientemente constante" para la práctica n que no importa.)