Python中列表的前n个最大值

Question

怎样才能从一个给定的列表中找到前n个最大的值呢？如果n的值相对来说比较小，而这个列表的长度又很长，有没有比下面这种方法更有效的方式呢：

alist.sort()
return alist[0:n]

Answer 1

你的方法很简洁，但可能不是效率最高的。有一种可能的改进方法是使用一种确定性选择算法（详细解释可以在这里的文字和这里的视频中找到）。然后你可以用这个算法来处理你想要的值。这样做的整体操作复杂度是O(n)，而且因为你是在处理一个列表，所以我认为你不太可能找到更好的方法。

Answer 2

使用heapq模块：

import heapq

return heapq.nlargest(n, l)        

如果你只想找出相对较少的n个元素，使用堆队列会比完全排序更有效率。如果n比较大，使用sorted(l)[-n:]会更有效。heapq.nlargest()这个功能会检查这些情况，如果发现n等于或大于列表的长度len(l)，它就会改用sorted()来处理。

需要注意的是，heapq模块会直接修改原来的列表（会对列表调用heapq.heapify()）。