从一亿个数字中检索前100个数字
我的一个朋友被问了一个问题
从一亿个数字中检索最大的100个数字
在最近的一次求职面试中 你有什么想法想出一个有效的方法来解决它？
将它们全部通过大小为100的最小堆运行：对于每个input数k ，用max(k, m)replace当前的最小m 。 之后堆保存了100个最大的input。
像Lucene这样的search引擎可以使用这种方法，通过改进来select最相关的search答案。
编辑：我没有面试 – 我得到的细节错了两次（之前完成这个，在生产）。 这是检查它的代码; 它几乎与Python的标准heapq.nlargest() ：
import heapq def funnel(n, numbers): if n == 0: return [] heap = numbers[:n] heapq.heapify(heap) for k in numbers[n:]: if heap[0] < k: heapq.heapreplace(heap, k) return heap >>> funnel(4, [3,1,4,1,5,9,2,6,5,3,5,8]) [5, 8, 6, 9]
好吧，这是一个非常愚蠢的答案，但它是一个有效的答案：
- 将所有1亿个条目加载到一个数组中
- 调用一些快速sorting的实现
- 取最后100个项目（按升序sorting），如果可以降序sorting，则前100个项目。
推理：
- 在这个问题上没有任何背景，所以效率可以被认为是有效的？ 电脑时间还是程序员时间？
- 这种方法可以很快实现。
- 1亿个条目 – 数字，只有几百MB，所以每一个体面的工作可以简单地运行。
对于某种一次性操作来说，这是一个很好的解决scheme。 它会吸每秒运行x次或其他东西。 但是，我们需要更多的上下文，因为mclientk也有他简单的SQL语句 – 假设内存中不存在1亿个数字是一个可行的问题，因为…他们可能来自数据库，大部分时间会说话关于业务相关的数字。
因此，这个问题真的很难回答 – 效率首先要被定义。
Mergesort分批100，那么只能保持前100名。
顺便提一句，你可以在各个方向上进行缩放，包括同时进行。
如果数据已经存在于可以修改的数组中，则可以使用Hoare's Selectalgorithm的变体，该algorithm是（依次）Quicksort的变体。
基本的想法很简单。 在Quicksort中，将数组分成两部分，一部分大于枢轴，另一部分小于枢轴。 然后你recursion地sorting每个分区。
在Selectalgorithm中，您完全按照以前的方式执行分区步骤 – 但是不是recursionsorting这两个分区，而是查看哪个分区包含所需的元素，并在该分区中仅recursion地select。 例如，假设您的1亿个项目分成几乎一半，那么前几个迭代将只考虑上面的分区。
最终，你可能会达到你想要“桥接”两个分区的那一点 – 例如，你有一个大约150个分区的分区，当你分区时，你最终得到两个~75个分区。 此时，只有一个小细节发生了变化：不是拒绝一个分区，只继续工作，而是接受 75个项目的上部分区，然后继续查找下部分区中的前25个分区。
如果你用C ++来完成这个工作，你可以用std::nth_element来完成这个工作（通常这个工作大致如上所述）。 平均而言，这是线性的复杂性，我相信这个复杂性和你所希望的一样好（没有一些先前存在的顺序，我没有看到任何方法去查找所有元素的前N个元素）。
如果数据不在数组中，而且（例如）从文件中读取数据，则通常需要使用堆。 你基本上读了一个项目，把它插入到堆中，如果堆大于你的目标（在这种情况下是100个项目），你删除一个并重新heapify。
可能不那么明显（但实际上是这样）的是，你通常不希望为这个任务使用最大堆。 乍一看，这似乎很明显：如果你想获得最大的项目，你应该使用最大的堆。
然而，从堆中“删除”的项目来考虑更简单。 最大的堆让你快速find堆中最大的一个物品。 然而，它不是为了在堆中find最小的项而优化的。
在这种情况下，我们主要关注堆中最小的项目。 特别是，当我们从文件中读取每个项目时，我们想把它与堆中最小的项目进行比较。 如果（且仅当）比堆中的最小项大时，我们想用新项replace堆中当前最小的项。 既然（根据定义）比现有的项目大，那么我们需要把它筛选到堆中的正确位置。
但是请注意：如果文件中的项目是随机排列的，当我们通过文件读取时，我们很快就会达到一个点，在这个点上，我们读入文件的大部分项会比堆中的最小项小。 由于我们可以轻松访问堆中最小的项目，所以比较起来相当快捷，对于较小的项目根本不会插入堆中。
TOP 100 ，你的意思是100最大？ 如果是这样：
SELECT TOP 100 Number FROM RidiculouslyLargeTable ORDER BY Number DESC
确保你告诉面试官，你认为表格是正确的索引。
没有理由对整个列表进行sorting。 这应该是在O（n）时间可行的。 在伪代码中：
List top = new List for each num in entireList for i = 0 to top.Length if num > top[i] then top.InsertBefore(num, i) if top.Length > 100 then top.Remove(top.Length - 1) end if exit for else if i = top.Length - 1 and i < 100 then top.Add(num) end if end if next next
@darius实际上可以改善！
通过“修剪”或根据需要推迟堆更换操作
假设我们在堆的顶部有一个= 1000
它有c，b兄弟姐妹
我们知道c，b> 1000
a=1000 +-----|-----+ b>a c>a We now read the next number x=1035 Since x>a we should discard a. Instead we store (x=1035, a=1000) at the root We do not (yet) bubble down the new value of 1035 Note that we still know that b,c<a but possibly b,c>x Now, we get the next number y when y<a<x then obviously we can discard it when y>x>a then we replace x with y (the root now has (y, a=1000)) => we saved log(m) steps here, since x will never have to bubble down when a>y>x then we need to bubble down y recursively as required Worst run time is still O(n log m) But average run time i think might be O(n log log m) or something In any case, it is obviously a faster implementation
对O（n）中的数组进行Heapify。 然后拿出前100名元素。
我存储了前100个数字的最大值 – 100的大小。
-
在最后一级，我跟踪最小号码和我插入的新号码，并用最小号码进行检查。其他号码是否是前100名的候选人。
– 我再次呼吁重新join，所以我总是有最大的堆100。
所以它的复杂性是O（nlogn）。
int numbers[100000000000] = {...}; int result[100] = {0}; for( int i = 0 ; i < 100000000000 ; i++ ) { for( int j = 0 ; j < 100 ; j++ ) { if( numbers[i] > result[j] ) { if( j < 99 ) { memcpy(result+j+1, result+j, (100-j)*sizeof(int)); } result[j] = numbers[i]; break; } } }
第一次迭代：
快速sorting，取顶部100. O（n log n）。 简单，易于编码。 非常明显。
更好？ 我们正在使用数字，做一个基数sorting（线性时间）排名前100。我希望这是面试官正在寻找。
任何其他的考虑？ 好吧，一百万个数字并不是很多的内存，但是如果你想最大限度地减less内存，你可以保持迄今为止所遇到的最多100个数字，然后只是扫描这些数字。 什么是最好的方法？
有些人提到了一堆，但更好的解决scheme可能是一个双链表，在那里你保持指针到目前为止发现的前100名的最低。 如果遇到列表中当前最小的数字a，则与下一个元素进行比较，并将数字从下一个移到当前，直到find新数字的位置。 （这基本上只是一个专门的情况堆）。 通过一些调整（如果数字大于当前最小值，与当前最大值比较以查看哪个方向行走列表以find插入点），这将是相对有效的，并且只需要1.5k的内存。
假设mylist是一个亿的数据清单。 所以我们可以对列表进行sorting，并从mylist中取出最后的数据。
mylist.sort（）
MYLIST [-100：]
第二种方式：
导入heapq
heapq.nlargest（100，mylist）
