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

Question

我想从至少1亿个数字列表中获取最大的100个元素.

我可以对整个列表进行排序,并从排序列表中获取最后100个元素,但就内存和时间而言,这将是非常昂贵的.

有没有现成的简单,pythonic方式这样做？

我想要的是跟随功能而不是纯粹的排序.其实我不想浪费时间来分类我不在乎的元素.

例如,这是我想要的功能:

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

请注意,此要求仅适用于性能视角.

Answer 1

标准库中的heapq模块提供了nlargest()函数来执行此操作:

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

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

Answer 2

选择算法应该有帮助.

一个非常简单的解决方案是找到第100个最大元素,然后通过列表挑选大于此元素的元素.这将给你100个最大的元素.这是列表长度的线性; 这是最好的.

还有更复杂的算法.一个堆,例如,是非常适合于这个问题.堆基于算法是n log k这里n是列表的长度,k是要选择最大元素的数量.

有关选择算法的维基百科页面上有关于此问题的讨论.

编辑:另一张海报指出Python有一个内置的解决方案来解决这个问题.显然这比滚动你自己容易得多,但我会保留这篇文章,以防你想了解这些算法是如何工作的.

Answer 3

您可以使用堆数据结构.堆不一定是有序的,但它是保存半有序数据的一种相当快的方法,并且它具有最小项始终是堆中第一个元素的好处.

堆有两个基本操作可以帮助您:添加和替换.

基本上你所做的就是添加项目,直到你得到100项(你的问题的前N个数字).然后,只要新项目大于第一项,就用每个新项目替换第一项.

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