jak skutecznie uzyskać k większe elementy listy w pythonie

Question

Jaki jest najbardziej wydajny, elegancki i pytonowy sposób rozwiązania tego problemu?

Biorąc pod uwagę listę (lub zestaw lub cokolwiek) z n elementów, chcemy uzyskać k największych. (Można zakładać k<n/2 bez utraty ogólności, tak myślę) Na przykład, jeśli lista byli:

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

n = 9, i powiedzmy, że k = 3. Jaki jest najbardziej efektywny algorytm do pobierania 3 największe? W takim przypadku powinniśmy uzyskać numer [9,8,7], bez żadnej określonej kolejności.

Dzięki! Manuel

Answer 1

Zastosowanie nlargest z modułem heapq

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

Można również dać klucz do nlargest w przypadku, gdy chce zmienić kryteria:

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

można użyć modułu 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

Prosty, O (n log n) sposobem jest, aby posortować listę następnie dostać ostatnie k elementy.

Właściwym sposobem jest użycie selection algorithm, który działa w czasie O (n + k log k).

Również, heapq.nlargesttakes O(n log k) time, które mogą ale nie muszą być wystarczająco dobre.

(Jeśli k = O (n), wszystkie 3 algorytmy mają taką samą złożoność (tzn. Nie przejmuj się) .Jeśli k = O (log n), algorytm wyboru opisany w Wikipedii to O (n) i heapq.nlargest jest O (n log log n), ale podwójny logarytm jest "wystarczająco stały" dla większości praktycznych n, że nie ma to znaczenia.)