如何从大量数字中获取最大的数字？

Question

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

我可以对整个列表进行排序，只需从排序后的列表中取出最后100个元素，但这在内存和时间上都非常昂贵。在

有没有现成的简单的Python式的方法？在

我想要的是以下函数，而不是纯排序。实际上，我不想浪费时间去整理我不在乎的元素。在

例如，这是我想要的函数：

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

注：此要求仅适用于性能方面。在

Answer 1

标准库中的heapq模块提供了nLarge（）函数来执行此操作：

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

它不会对整个列表进行排序，因此您不会在不需要的元素上浪费时间。在

Answer 2

可以使用堆数据结构。堆不一定是有序的，但它是保持半有序数据的一种相当快的方法，而且它的好处是最小的项总是堆中的第一个元素。在

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

基本上你要做的就是在上面加上一个项目，直到你得到100个项目（每个问题的前N个数字）。然后，用每个新项替换第一项，只要新项大于第一项。在

每当你用更大的东西替换第一个项目时，堆中的内部代码会调整堆的内容，这样如果新的项目不是最小的，它将冒泡到堆中，最小的项目将“冒泡”到第一个元素，随时可以被替换。在

Answer 3

Selection algorithms应该有帮助。在

一个非常简单的解决方案是找到第100个最大的元素，然后在列表中找出比这个元素大的元素。这将给你100个最大的元素。列表的长度是线性的；这是最好的。在

还有更复杂的算法。例如，heap就很容易解决这个问题。基于堆的算法是n log k，其中n是列表的长度，k是要选择的最大元素数。在

在Wikipedia页面上有一个关于这个选择算法的讨论。在

编辑：另一张海报指出Python有一个内置的解决方案来解决这个问题。很明显，这比你自己动手要容易得多，但我会继续写这篇文章，以防你想了解这些算法是如何工作的。在