Wie man effizient die k größeren Elemente einer Liste in Python bekommt

Question

Was ist die effizienteste, eleganteste und pythonischste Art, dieses Problem zu lösen?

Gegeben eine Liste (oder Menge oder was auch immer) von n Elementen, wir wollen die k größten bekommen. (Sie können k<n/2 ohne Beschränkung der Allgemeinheit annehmen, ich denke) Zum Beispiel, wenn die Liste waren:

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

n = 9, und wir k sagen = 3. Was ist der effizienteste Algorithmus ist für die 3 Abrufen die größten? In diesem Fall sollten wir [9,8,7], in keiner bestimmten Reihenfolge erhalten.

Danke! Manuel

Answer 1

Verwenden nlargest von heapq Modul

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

Sie auch einen Schlüssel für den Fall nlargest geben können wollen Sie Ihre Kriterien ändern:

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

Sie können das heapq Modul .

>>> 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

Die einfache, O (n log n) Weg ist, um die Liste dann ist die letzten k Elemente zu sortieren.

Der richtige Weg ist die Verwendung einer selection algorithm, die in O (n + k log k) Zeit läuft.

Auch heapq.nlargesttakes O(n log k) time, die möglicherweise oder nicht gut genug sein können.

(Wenn k = O (n), dann haben alle 3 Algorithmen die gleiche Komplexität (dh stört sie nicht.) Wenn k = O (log n), dann ist der in Wikipedia beschriebene Auswahlalgorithmus O (n) und heapq.nlargest ist O (n log log n), aber Doppel-Logarithmus ist "konstant genug" für die meisten praktischen n, dass es egal ist.)