come ottenere in modo efficiente i k elementi più grandi di una lista in python

Question

Qual è il modo più efficiente, elegante e pietoso per risolvere questo problema?

Dato un elenco (o insieme o altro) di n elementi, vogliamo ottenere i k più grandi. (Si può assumere k<n/2 senza perdita di generalità, immagino) Ad esempio, se la lista fosse:

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

n = 9, e diciamo k = 3. Qual è l'algoritmo più efficace per recuperare il 3 i più grandi? In questo caso dovremmo ottenere [9,8,7], in nessun ordine particolare.

Grazie! Manuel

Answer 1

Usa nlargest dal modulo heapq

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

Si può anche dare una chiave per nlargest nel caso in cui si desidera cambiare i criteri di:

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

È possibile utilizzare il modulo 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

La semplice, O (n log n) modo è quello di ordinare l'elenco quindi ottenere gli ultimi k elementi.

Il modo corretto è utilizzare un selection algorithm, che viene eseguito in tempo O (n + k log k).

Inoltre, heapq.nlargesttakes O(n log k) time, che può essere o non essere abbastanza buono.

(Se k = O (n), allora tutti e 3 gli algoritmi hanno la stessa complessità (vale a dire non disturbare). Se k = O (log n), allora l'algoritmo di selezione come descritto in Wikipedia è O (n) e heapq.nlargest è O (n log log n), ma il doppio logaritmo è "abbastanza costante" per la maggior parte pratico n che non ha importanza.)