Python >> Python-zelfstudie >  >> Python

hoe efficiënt de k grotere elementen van een lijst in python te krijgen

Gebruik de grootste van heapq-module

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

Je kunt ook een sleutel geven aan nlargest als je je criteria wilt wijzigen:

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

De eenvoudige, O(n log n) manier is om de lijst te sorteren en dan de laatste k . te krijgen elementen.

De juiste manier is om een ​​selectie-algoritme te gebruiken dat in O(n + k log k) tijd loopt.

Ook heapq.nlargest kost gemiddeld O(k log n) tijd, wat al dan niet goed genoeg is.

(Als k =O(n), dan hebben alle 3 de algoritmen dezelfde complexiteit (dus doe geen moeite). Als k =O(log n), dan is het selectiealgoritme zoals beschreven in Wikipedia O(n) en heapq.nlargest is O(n log log n), maar dubbele logaritme is "constant genoeg" voor de meest praktische n dat het er niet toe doet.)


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

sorted(l)[-k:]