how to efficiently get the k bigger elements of a list in python

Question

Hi! What´s the most efficient, elegant and pythonic way of solving this problem?

Given a list (or set or whatever) of n elements, we want to get the k biggest ones. ( You can assume k<n/2 without loss of generality, I guess) For example, if the list were:

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

n = 9, and let's say k = 3. What's the most efficient algorithm for retrieving the 3 biggest ones? In this case we should get [9,8,7], in no particular order.

Thanks! Manuel

Answer 1

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

sorted(l)[-k:]

Answer 2

Use nlargest from heapq module

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

You can also give a key to nlargest in case you wanna change your criteria:

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 3

You can use the heapq module.

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

The simple, O(n log n) way is to sort the list then get the last k elements.

The proper way is to use a selection algorithm, which runs in O(n + k log k) time.

Also, heapq.nlargest takes O(n log k) time, which may or may not be good enough.

(If k = O(n), then all 3 algorithms have the same complexity (i.e. don't bother). If k = O(log n), then the selection algorithm as described in Wikipedia is O(n) and heapq.nlargest is O(n log log n), but double logarithm is "constant enough" for most practical n that it doesn't matter.)

Answer 6

WARNING: NO GOOD FOR PERFORMANCE.
I am learning functional programming these days! :-)

Recursive function to get k max elements.

def rec_get_k_max(lst,k):
    if k == 0 or len(lst)==0 :
        return []
    else:
        m = max(lst)
        lst.remove(m)
        mx_lst = [m] + rec_get_k_max(lst,k-1)
        return mx_lst

if __name__=='__main__':
    ll = [9,1,6,4,2,8,3,7,5]
    print rec_get_k_max(ll,3)