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

StackOverflow https://stackoverflow.com/questions/1218922

  •  10-07-2019
  •  | 
  •  

题

我想从至少 100000000 个数字的列表中获取最大的 100 个元素。

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

有没有现有的简单的、Python 式的方法来做到这一点？

我想要的是跟随函数而不是纯粹的排序。其实我不想浪费时间来对我不关心的元素进行排序。

例如，这是我想要的功能：

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

请注意，此要求仅用于性能角度。

有帮助吗？

解决方案

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

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

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

其他提示

选择算法应该对此有所帮助。

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

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

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

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

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

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

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

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

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

虽然您不关心结果是否排序，但直观显而易见，您将免费获得此结果。为了知道您拥有前100名，您需要通过一些有效的数据结构按顺序订购当前的热门号码列表。该结构将以某种自然的方式知道每个元素的最小值，最大值和相对位置，您可以断言它在其邻居旁边的位置。

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

这是我使用的解决方案，该解决方案独立于库，它将使用具有数组的任何编程语言来工作：

初始化：

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将很快获得高价值，因此，仅需要将输入列表中的大多数值与MinValue进行比较（比较的结果主要是错误的）。

对于观众中的算法：你可以通过Tony Hoare算法的简单变体来做到这一点 查找 ：

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，的第一个<=>元素中，而不用对它们进行排序。当然，如果你想要对它们进行排序，或者为了简单起见，堆更好，并且调用库函数仍然更好。但这是一个很酷的算法。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top