Python：从列表中取最大N个元素

Question

有没有什么函数可以让我从一个列表中返回前N个最高的元素呢？

比如说，如果 max(l) 是用来找出列表中最大的一个元素，那么类似 max(l, count=10) 这样的函数就可以返回前10个最大的数字（如果列表 l 的元素少于10个，那就返回所有的）。

或者，有没有什么简单又高效的方法可以得到这些最高的元素？（除了那些明显的标准方法；另外，也不想先把整个列表排序，因为那样效率太低了，相比于标准的方法。）

Answer 1

首先，从列表L中取出前10个数，叫它X。记下X中的最小值。

然后，遍历列表L中剩下的每个元素L[i]。

如果L[i]比X中的最小值大，就把X中的最小值去掉，然后把L[i]放进去。你可能需要把X保持为一个有序的链表，并进行插入操作。记得更新X中的最小值。

最后，你就得到了X中最大的10个值。

我猜这个过程的复杂度是O(kN)（这里的k是10），因为插入排序是线性的。这可能是gsl使用的方法，如果你能看懂一些C语言的代码：

http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html

可能在numpy中也有类似的功能。

Answer 2

标准库中用来实现这个功能的函数是 heapq.nlargest

Answer 3

heapq.nlargest:

>>> import heapq, random
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100)))
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254]