2010-02-11 2 views
15

Was ist die effizienteste, eleganteste und pythonischste Art, dieses Problem zu lösen?Wie man effizient die k größeren Elemente einer Liste in Python bekommt

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

+0

+1 Jetzt, dass Grundzweck bedient wird, lassen Sie CODE- GOLF? –

Antwort

33

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) ] 
+0

+1: Ich wusste nicht über dieses Modul ... danke – mshsayem

+0

Great Language Ranking :)) –

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

sorted(l)[-k:] 
+0

Das ist schöner als meins) – Rorick

+0

... aber es funktioniert nicht in dem sehr speziellen Fall von k == 0. :) – EOL

4

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] 
>>> 
+2

wir brauchen es hier nicht zu häufen – garg10may

4
sorted(l, reverse=True)[:k] 
7

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