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

发布于 2024-08-01 13:08:10 字数 317 浏览 9 评论 0原文

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

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

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

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

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

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

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

原文

I'd like to get the largest 100 elements out from a list of at least 100000000 numbers.

I could sort the entire list and just take the last 100 elements from the sorted list, but that would be very expensive in terms of both memory and time.

Is there any existing easy, pythonic way of doing this?

What I want is following function instead of a pure sort. Actually I don't want waste time to sort the elements I don't care.

For example, this is the function I'd like to have:

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

Note this requirement is only for performance perspective.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

开始看清了 2024-08-08 13:08:10

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

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

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

The heapq module in the standard library offers the nlargest() function to do this:

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

It won't sort the entire list, so you won't waste time on the elements you don't need.

回复收藏 0 原文

浅浅淡淡 2024-08-08 13:08:10

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

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

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

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

回复收藏 0 原文

○闲身 2024-08-08 13:08:10

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

一个非常简单的解决方案是找到第 100 个最大的元素，然后遍历列表，挑选出比该元素大的元素。这将为您提供 100 个最大的元素。这与列表的长度成线性关系；这是最好的可能。

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

选择算法的维基百科页面上对此问题进行了讨论。

编辑：另一位发帖者指出，Python 有一个内置的解决方案来解决这个问题。显然，这比自己动手要容易得多，但我会保留这篇文章，以防您想了解此类算法的工作原理。

回复收藏 0 原文

心房的律动 2024-08-08 13:08:10

对于观众中的算法新手：您可以通过 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 的第一个 topn 元素中，没有对它们进行排序。当然，如果您希望对它们进行排序，或者为了纯粹的简单性，堆更好，并且调用库函数更好。但这是一个很酷的算法。

For the algorithms weenies in the audience: you can do this with a simple variation on Tony Hoare's algorithm 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)

This algorithm puts the largest topn elements into the first topn elements of array a, without sorting them. Of course, if you want them sorted, or for sheer simplicity, a heap is better, and calling the library function is better still. But it's a cool algorithm.

回复收藏 0 原文

执着的年纪 2024-08-08 13:08:10

这是我使用过的一个独立于库的解决方案
将在任何具有数组的编程语言中工作：

初始化：

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

Here is a solution I have used that is independent of libraries and that
will work in any programming language that has arrays:

Initialisation:

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.

For each value, say current_value, in the input list:

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 will quickly get a high value and thus most values
in the input list will only need to be compared to minvalue
(the result of the comparison will mostly be false).

回复收藏 0 原文