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

我想从至少100000000个数字的列表中获得最大的100个元素。如何从大量的数字中获得最大的数字？

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

是否有任何现有的简单，pythonic这样做？

我想要的是下面的功能，而不是纯粹的排序。其实我不想浪费时间来排序我不在乎的元素。

例如，这是我想拥有的功能：

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

注意这一要求仅适用于性能的角度来看。

来源

2009-08-02 limi

标准库的heapq模块提供nlargest（）函数来做到这一点：

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

它不会排序整个列表，这样你就不会在你不”的元素浪费时间需要。

来源

2009-08-02 13:54:27

你走了。我只是想提出一个优先级队列将是一个很好的方法来处理这与我所建议的算法相结合。不是一个Python程序员，我没有意识到它已经可用。 – tvanfosson 2009-08-02 13:58:24

Selection algorithms应该可以帮到这里。

一个非常简单的解决方案是找到第100个最大的元素，然后遍历列表选取比这个元素大的元素。那会给你100个最大的元素。这在列表的长度上是线性的;这是最好的。

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

在Wikipedia页面上有关于选择算法的此problem的讨论。

编辑：另一张海报指出，Python有一个内置的解决这个问题的方法。显然，这比自己编写起来容易得多，但如果您想了解这些算法的工作原理，我会保留这篇文章。

来源

2009-08-02 13:45:45 jason

在你描述的解决方案中，为了“找到第100个最大元素”，这不是意味着你已经找到了100个最大元素的列表吗？ – 2009-08-04 22:25:50

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

堆有两个基本的操作，这将有助于你：添加和替换。

基本上你要做的就是将项目添加到它，直到你得到一个100个项目（根据您的问题，您的前N个号码）。之后，只要新项目大于第一个项目，就用每个新项目替换第一个项目。

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

来源

2009-08-02 13:53:21

执行此操作的最佳方法是维护堆排序的优先级队列，一旦它有100个条目，就会弹出它。

虽然你不在乎结果是否排序，但直观上显而易见，你将免费得到这个结果。为了知道你有前100名，你需要通过一些有效的数据结构来排序你最新的顶级数字。该结构将以某种自然的方式知道每个元素的最小值，最大值和相对位置，您可以断言它的位置与它的邻居位置相邻。

正如在python中提到的那样，你会使用heapq。在java中的PriorityQueue： http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

来源

2009-08-02 13:59:47 groundhog

这里是我使用的是独立库的解决办法，将在具有阵列的任何编程语言的工作：

初始化：

Make an array of 100 elements and initialise all elements 
with a low value (less than any value in your input list). 

Initialise an integer variable to 0 (or any value in 
[0;99]), say index_minvalue, that will point to the 
current lowest value in the array. 

Initialise a variable, say minvalue, to hold the current 
lowest value in the array.

对于每个值，例如current_value，在输入列表中：

if current_value > minvalue 

    Replace value in array pointed to by index_minvalue 
    with current_value 

    Find new lowest value in the array and set index_minvalue to 
    its array index. (linear search for this will be OK as the array 
    is quickly filled up with large values) 

    Set minvalue to current_value 

else 
    <don't do anything!>

minvalue wil我很快就会得到一个很高的值，因此输入列表中的大部分值只需要与最小值比较（比较的结果大部分是错误的）。

来源

2009-08-02 15:09:29

对于观众算法怪人：你可以与托尼·霍尔的算法Find一个简单的变化做到这一点：

find(topn, a, i, j) 
    pick a random element x from a[i..j] 
    partition the subarray a[i..j] (just as in Quicksort) 
    into subarrays of elements <x, ==x, >x 
    let k be the position of element x 
    if k == 0 you're finished 
    if k > topn, call find(topn, a, i, k) 
    if k < topn, call find(topn-k, k, j)

该算法把最大topn元素融入到阵列a，的第一topn元素没有排序它们。当然，如果你想将它们排序，或者非常简单，堆会更好，并且调用库函数仍然更好。但这是一个很酷的算法。

来源

2009-08-02 16:45:34

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

回答

相关问题