10

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

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

是否有任何现有的简单、pythonic 方式来执行此操作？

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

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

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

请注意，此要求仅用于性能方面。

4

6 回答 6

27

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

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

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

于 2009-08-02T13:54:27.990 回答
6

选择算法在这里应该有所帮助。

一个非常简单的解决方案是找到第 100 个最大的元素，然后遍历列表挑选比该元素更大的元素。这将为您提供 100 个最大的元素。这在列表的长度上是线性的；这是最好的办法。

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

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

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

于 2009-08-02T13:45:45.473 回答
5

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

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

基本上，您所做的就是向其中添加项目，直到达到 100 个项目（每个问题的前 N ​​个数字）。然后之后，只要新项目大于第一个项目，就用每个新项目替换第一个项目。

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

于 2009-08-02T13:53:21.190 回答
3

最好的方法是维护一个堆排序的优先级队列，一旦它有 100 个条目，您就会弹出该队列。

虽然您不在乎结果是否已排序，但很明显您将免费获得此结果。为了知道你有前 100 名，你需要通过一些有效的数据结构来排序你当前的前 100 名列表。该结构将以某种自然的方式知道每个元素的最小值、最大值和相对位置，您可以断言它的位置在它的邻居旁边。

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

于 2009-08-02T13:59:47.047 回答
2

这是我使用的一个独立于库的解决方案，它适用于任何具有数组的编程语言：

初始化：

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 进行比较（比较的结果大多为 false）。

于 2009-08-02T15:09:29.267 回答
1

对于观众中的小算法：您可以通过 Tony Hoare 的算法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元素放入topn数组的第一个元素中a，而不对它们进行排序。当然，如果你想让它们排序，或者为了简单起见，堆更好，调用库函数更好。但这是一个很酷的算法。

于 2009-08-02T16:45:34.963 回答