我正在编写一个程序，而不是需要在一组数字中找到第 N 个最大值。这些数字是由程序生成的，但我没有足够的内存来存储 N 个数字。是否有比 N 更好的存储上限？数字组（以及 N）大小的上限约为 100,000,000。
注意：数字是小数，列表可以包含重复项。
[编辑]：我的内存限制是 16 MB。
问问题
2528 次
5 回答
3
你能从一开始就重新生成同一组数字吗？如果是这样，您可以对输出进行多次传递：首先找到最大值，重新启动生成器，找到小于该值的最大值，重新启动生成器，然后重复此操作，直到得到结果。
这将是一个真正的性能杀手，因为你有很多数字并且需要很多遍 - 但是在内存方面，你只需要存储 2 个元素（当前最大值和“限制”，数字你在最后一次通过时找到的）和一个通行证柜台。
您可以通过使用优先级队列来查找最大的 M 个元素（选择一些可以放入内存的 M）来加快速度，从而将所需的通过次数减少到 N/M。
例如，如果您需要在 15 个数字的列表中找到第 10 个最大的元素，则可以通过相反的方式来节省时间。由于它是第 10 大元素，这意味着有 15-10=5 个元素比该元素小 - 所以您可以寻找第 6 小的元素。
于 2009-07-05T16:55:52.867 回答
3
这是一个多通道算法（因此，您必须能够多次生成相同的列表，或者将列表存储到辅助存储中）。
第一关：
- 找出最大值和最小值。那是你的初始范围。
在第一个之后通过：
- 将范围划分为 10 个等间距的箱。我们不需要在 bin 中存储任何数字。我们只是要计算垃圾箱中的成员。所以我们只有一个整数数组（或 bigints——只要能准确地保存我们的计数）请注意，10 是 bin 数量的任意选择。您的样本量和分布将决定最佳选择。
- 遍历数据中的每个数字，增加您看到的数字所在的 bin 的计数。
- 找出哪个箱子有你的答案，并将该箱子上方的数字添加到获胜箱子上方的数字计数中。
- 获胜箱的顶部和底部范围是您的新范围。
- 再次循环执行这些步骤，直到您有足够的内存来保存当前 bin 中的数字。
最后一关：
- 您现在应该知道当前 bin 上方有多少数字。
- 您有足够的存储空间来获取当前垃圾箱范围内的所有数字，因此您可以旋转并获取实际数字。只需对它们进行排序并获取正确的数字。
示例：如果您看到的范围是 0.0 到 1000.0，那么您的 bin 范围将是：
(- 0.0 - 100.0]
(100.0 - 200.0]
(200.0 - 300.0]
...
(900.0 - 1000.0)
如果您通过计数发现您的号码在 (100.0 - 2000.0] 箱中，那么您的下一组箱将是：
(100.0 - 110.0]
(110.0 - 120.0]
etc.
另一个多通道想法：
只需进行二进制搜索。选择范围的中点作为第一个猜测。您的通行证只需要进行高于/低于计数来确定下一个估计值（可以按计数加权，或为代码简化而采用简单的平均值）。
于 2009-07-05T18:05:54.463 回答
1
这类似于另一个问题 - C 程序在不排序的情况下搜索数组中的第 n 个最小元素？——你可能会得到一些答案。
该逻辑同样适用于第 N 个最大/最小搜索。
注意：我并不是说这是重复的。
由于您有很多（近 10 亿？）数字，这是空间优化的另一种方法。
让我们假设您的数字适合 32 位值，因此大约 10 亿将需要接近 32GB 的空间。现在，如果你能负担得起大约 128MB 的工作内存，我们可以一次性完成。
- 想象一个存储为 32 位字数组的 10 亿位向量
- 让它初始化为全零
- 开始遍历您的数字并继续为数字的值设置正确的位位置
- 当您完成一次通过时，从该位向量的开头开始计数第 N 个设置位
- 该位的位置为您提供了第 N 个最大数字的值
- 您实际上已经对过程中的所有数字进行了排序（但是，不跟踪重复数）
于 2009-07-05T16:50:50.140 回答
0
如果我理解得很好，你的程序的内存使用上限是 O(N)（可能是 N+1）。您可以维护一个大于当前 X（迄今为止的第 N 个最大值）的生成值列表，按最低优先排序。一旦生成了一个新的更大的值，您可以将当前的 X 替换为列表的第一个元素，并将刚刚生成的值插入到其在列表中的相应位置。
于 2009-07-05T16:36:09.170 回答
0
排序-n | uniq -c 并且第 N 行应该是第 N 行
于 2009-07-05T16:50:44.710 回答