从一亿个数字中检索前100个数字

Question

我的一个朋友被问到一个问题

从一亿个数字中检索最大前100个数字

在最近的一次面试中.你有什么想法想出一个有效的解决方法吗？

Answer 1

通过大小为100 的最小堆运行它们:对于每个输入数字k,用当前的min m替换max(k, m).之后堆拥有100个最大输入.

像Lucene这样的搜索引擎可以使用这种方法进行改进,以选择最相关的搜索答案.

编辑:我没有通过面试 - 我的细节错了两次(之前完成了这个,在制作中).这是检查它的代码; 它与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]

Answer 2

好的,这是一个非常愚蠢的答案,但它是一个有效的答案:

• 将所有1亿个条目加载到数组中
• 在上面调用一些快速排序实现
• 取最后100项(按升序排序),如果可以降序排序,则前100项.

推理:

• 这个问题没有背景,所以可以提出效率 - 有效率是多少？电脑时间还是程序员时间？
• 这种方法可以非常快速地实现.
• 1亿个条目 - 数字,只有几百mb,因此每个体面的工作站都可以简单地运行.

对于某种一次性操作,这是一个很好的解决方案.它会每秒运行x次或其他东西.但是,我们需要更多的上下文 - 正如mclientk也有他简单的SQL语句 - 假设内存中不存在1亿个数字是一个可行的问题,因为......它们可能来自数据库,大部分时间都会在谈话时关于商业相关数字.

因此,这个问题很难回答 - 首先必须确定效率.

Answer 3

Mergesort分批100个,然后只保留前100名.

顺便提一下,您可以在各种方向上进行缩放,包括同时进行.

Answer 4

如果数据已经存在于您可以修改的数组中,则可以使用Hoare选择算法的变体,该算法(反过来)是Quicksort的变体.

基本想法很简单.在Quicksort中,您将阵列分为两部分,一部分大于枢轴,另一部分小于枢轴.然后递归排序每个分区.

在Select算法中,您完全像以前一样执行分区步骤 - 但不是递归地对两个分区进行排序,而是查看哪个分区包含您想要的元素,并在该分区中以递归方式选择.例如,假设您的1亿个项目几乎分成两半,前几次迭代您只会查看上层分区.

最终,您可能会达到一个点,您想要的部分"桥接"两个分区 - 例如,您有一个约150个数字的分区,当您进行分区时,最终会得到两个约75个分区.此时,只有一个小细节发生变化:您不接受拒绝一个分区而只继续工作另一个分区,而是接受 75个项目的上部分区,然后继续查找下部分区中的前25个分区.

如果你在C++中这样做,你可以这样做std::nth_element(通常大致如上所述实现).平均而言,这具有线性复杂性,我认为这与你所希望的一样好(没有一些预先存在的顺序,我没有看到任何方法在没有查看所有元素的情况下找到前N个元素).

如果数据不在数组中,并且您(例如)从文件中读取数据,则通常需要使用堆.您基本上读取一个项目,将其插入堆中,如果堆大于您的目标(在这种情况下为100个项目),则删除一个项目并重新堆积.

什么可能不那么明显(但实际上是真的)是你通常不想使用max-heap来完成这项任务.乍一看,它似乎很明显:如果你想获得最大的项目,你应该使用最大堆.

但是,根据您从堆中"移除"的项目来考虑更简单.最大堆可以让您快速找到堆中最大的一个项目.但是,它并未针对查找堆中的最小项进行优化.

在这种情况下,我们主要感兴趣的是堆中的最小项.特别是,当我们从文件中读取每个项目时,我们希望将它与堆中的最小项目进行比较.如果(并且仅当)它大于堆中的最小项,我们希望用新项替换当前堆中的最小项.由于(根据定义)大于现有项目,我们需要将其筛选到堆中的正确位置.

但是请注意:如果文件中的项目是随机排序的,当我们读取文件时,我们很快就会达到一个点,在这一点上,我们读入文件的大多数项目都会小于我们堆中的最小项目.由于我们可以轻松访问堆中的最小项,因此可以非常快速轻松地进行比较,而对于较小的项永远不会在堆中插入.