Python: prendi max N elementi da qualche lista

Question

C'è qualche funzione che mi restituirà gli N elementi più alti da qualche lista?

I.e. se max(l) restituisce il singolo elemento più alto, sth. come max(l, count=10) mi restituirebbe un elenco dei 10 numeri più alti (o meno se l è più piccolo).

O quale sarebbe un modo semplice ed efficace per ottenere questi? (Tranne l'ovvia implementazione canonica, inoltre, nessuna di queste cose comporta l'ordinamento dell'intera lista perché sarebbe inefficiente rispetto alla soluzione canonica.)

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 soluzione abbastanza efficiente è una variante di quicksort dove la ricorsione è limitata al parte destra del perno fino a quando la posizione del punto di rotazione è superiore al numero di elementi richiesti (con alcune condizioni extra per trattare i casi di confine, ovviamente).

La libreria standard ha heapq.nlargest, come indicato da altri qui.

Answer 3

Iniziare con il primo 10 da L, chiamare tale X. Nota il valore minimo di X.

Loop supera L [i] per i nell'arco resto L.

Se L [i] è maggiore di min (X), rilascia min (X) da X e inserisci L [i]. Potrebbe essere necessario mantenere X come elenco collegato ordinato e fare un inserimento. Aggiornamento min (X).

Alla fine, si ha la 10 valori più grandi X.

ho il sospetto che sarà O (kN) (dove k è 10 qui) dal momento che insertion sort è lineare. Potrebbe essere quello che utilizza GSL, quindi se si può leggere qualche codice C:

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

Probabilmente qualcosa in NumPy che fa questo.

Answer 4

La funzione della libreria standard che fa questo è heapq.nlargest