Alex Rivera | Logout

How to efficiently get the k bigger elements of a list?

Asked 2010-02-11T09:47:17.370
38

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

algorithm sorting performance python
Edit
Report

1 Answer

74

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) ]
answered 2010-02-11T09:50:45.513

Your Answer