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

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

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

 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 recuperar los 3 más grandes? En este caso deberíamos obtener [9,8,7] , sin ningún orden en particular.

¡Gracias! Manuel

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

Utilice nlargest desde el 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 a nlargest en caso de que quiera 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) ] 

La forma simple, O (n log n) es ordenar la lista y luego obtener los últimos k elementos.

La forma correcta es usar un algoritmo de selección , que se ejecuta en tiempo O (n + k log k).

Además, heapq.nlargest toma tiempo O (n log k) , que puede o no ser lo suficientemente bueno.

(Si k = O (n), entonces los 3 algoritmos tienen la misma complejidad (es decir, no molestan). Si k = O (registro n), entonces 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 mayoría de las prácticas n no importa.

 l = [9,1,6,4,2,8,3,7,5] sorted(l)[-k:] 

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] >>> 
 sorted(l, reverse=True)[:k]