如何从大量数字中找出最大值？

Question

我想从一个至少有一亿个数字的列表中找出最大的100个元素。

我可以把整个列表排序，然后直接取出排序后最后的100个元素，但这样在内存和时间上都非常耗费。

有没有什么简单的、符合Python风格的方法可以做到这一点呢？

我想要的是一个函数，而不是单纯的排序。其实我不想浪费时间去排序那些我不关心的元素。

比如说，我想要这样的一个函数：

getSortedElements(100, lambda x,y:cmp(x,y))

请注意，这个要求主要是从性能的角度考虑。

Answer 1

你可以使用一个叫做堆的数据结构。堆里的数据不一定是完全有序的，但它是一种比较快速的方式来保持半有序的数据，而且它的一个好处是最小的元素总是放在堆的最前面。

堆有两个基本操作可以帮助你：添加和替换。

简单来说，你就是把数据添加到堆里，直到你有100个项目（也就是你问题中提到的前N个）。然后在这之后，每当有新数据进来时，如果这个新数据比堆里第一个数据大，你就用新数据替换掉第一个数据。

每当你用一个更大的数据替换掉第一个数据时，堆内部的代码会自动调整堆里的内容，这样如果新数据不是最小的，它会“冒泡”到堆的上面，而最小的数据则会“冒泡”到最前面，准备好被替换。

Answer 2

选择算法可以在这里帮到你。

一个很简单的解决办法是先找到第100大的元素，然后遍历整个列表，挑选出比这个元素大的所有元素。这样你就能得到100个最大的元素。这种方法的效率是和列表长度成正比的，已经是最好的方法了。

还有一些更复杂的算法。比如说，堆这种数据结构就很适合解决这个问题。基于堆的算法效率是 n log k，其中 n 是列表的长度，k 是你想要选择的最大的元素个数。

关于这个 问题，维基百科的选择算法页面上有讨论。

补充：另一位网友提到，Python有内置的解决方案来处理这个问题。显然，这比自己实现要简单得多，但我还是保留这个帖子，以便你想了解这些算法是如何工作的。

Answer 3

标准库中的heapq模块提供了一个叫做nlargest()的函数，可以用来实现这个功能：

top100 = heapq.nlargest(100, iterable [,key])

这个函数不会对整个列表进行排序，所以你不会浪费时间在那些不需要的元素上。