如何在python中有效地获取列表中k个更大的元素

Question

什么是最有效,优雅和pythonic解决这个问题的方法？

给定n个元素的列表(或集合或其他),我们希望得到k个最大元素.(你可以假设k<n/2不失一般性,我猜)例如,如果列表是:

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

n = 9,让我们说k = 3.检索3个最大的算法最有效的算法是什么？在这种情况下,我们应该[9,8,7]没有特别的顺序.

谢谢!曼努埃尔

Answer 1

使用heapq模块中的nlargest

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

如果您想更改标准,还可以给出一个关键词:

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

简单的O(n log n)方法是对列表进行排序,然后获取最后的k个元素.

正确的方法是使用选择算法,该算法在O(n + k log k)时间内运行.

此外,heapq.nlargest 需要O(n log k)时间,这可能是也可能不够好.

(如果k = O(n),那么所有3种算法都具有相同的复杂度(即不要打扰).如果k = O(log n),那么维基百科中描述的选择算法是O(n)并且heapq.nlargest是O (n log log n),但对于大多数实际的n来说,双对数是"足够常量的" 并且无关紧要.)

Answer 3

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

sorted(l)[-k:]