查找十亿个文件中的一百个最大数字

Question

我今天去接受采访,被问到这个问题:

假设您有10亿个整数在磁盘文件中未分类.你如何确定最大的一百个数字？

我甚至不确定从哪里开始这个问题.给出正确结果的最有效流程是什么？我是否需要通过磁盘文件一百次获取我的列表中尚未包含的最高数字,或者是否有更好的方法？

Answer 1

显然,采访者希望你指出两个关键事实:

• 您无法将整个整数列表读入内存,因为它太大了.所以你必须逐一阅读.
• 您需要一个有效的数据结构来容纳100个最大的元素.此数据结构必须支持以下操作:
  • Get-Size:获取容器中的值的数量.
  • Find-Min:获得最小的价值.
  • Delete-Min:删除最小值以使用新的更大值替换它.
  • Insert:将另一个元素插入容器中.

通过评估数据结构的要求,计算机科学教授希望您建议使用Heap(Min-Heap),因为它旨在完全支持我们需要的操作.

例如,对于斐波那契堆,操作Get-Size,Find-Min和Insert所有都O(1)和Delete-Min是O(log n)(与n <= 100在这种情况下).

实际上,您可以使用您喜欢的语言标准库(例如,priority_queue来自#include <queue>C++)的优先级队列,该队列通常使用堆来实现.

Answer 2

这是我的初始算法:

create array of size 100 [0..99].
read first 100 numbers and put into array.
sort array in ascending order.
while more numbers in file:
    get next number N.
    if N > array[0]:
        if N > array[99]:
            shift array[1..99] to array[0..98].
            set array[99] to N.
        else
            find, using binary search, first index i where N <= array[i].
            shift array[1..i-1] to array[0..i-2].
            set array[i-1] to N.
        endif
    endif
endwhile

这有(非常轻微)的优点是前100个元素没有O(n ^ 2)混洗,只有O(n log n)排序,你可以很快识别并丢弃那些太小的元素.它还使用二进制搜索(最多7次比较)来找到正确的插入点,而不是50(平均)用于简单的线性搜索(不是我建议其他人提供这样的解决方案,只是它可能会给面试官留下深刻的印象) ).

您甚至可以获得奖励积分,建议使用C语言中的优化shift操作memcpy,前提是您可以确保重叠不是问题.

您可能要考虑的另一种可能性是维护三个列表(每个列表最多100个整数):

read first hundred numbers into array 1 and sort them descending.
while more numbers:
    read up to next hundred numbers into array 2 and sort them descending.
    merge-sort lists 1 and 2 into list 3 (only first (largest) 100 numbers).
    if more numbers:
        read up to next hundred numbers into array 2 and sort them descending.
        merge-sort lists 3 and 2 into list 1 (only first (largest) 100 numbers).
    else
        copy list 3 to list 1.
    endif
endwhile

我不确定,但最终可能比持续改组更有效率.

合并排序是一个简单的选择(对于合并排序列表1和2到3):

list3.clear()
while list3.size() < 100:
    while list1.peek() >= list2.peek():
        list3.add(list1.pop())
    endwhile
    while list2.peek() >= list1.peek():
        list3.add(list2.pop())
    endwhile
endwhile

简单地说,由于它们已经按降序排序,因此将前100个值从组合列表中拉出来.我没有详细检查是否会更有效,我只是提供它作为一种可能性.

我怀疑采访者会对"开箱即用"思维的可能性以及你说应该对其性能进行评估这一事实印象深刻.

与大多数采访一样,技术技能是他们所关注的事情之一.

Answer 3

创建一个包含100个数字的数组,全部为-2 ^ 31.

检查从磁盘读取的第一个数字是否大于列表中的第一个数字.如果是将数组复制为1索引并将其更新为新数字.如果没有,请检查100中的下一个,依此类推.

当你读完所有10亿个数字后,你应该拥有阵列中最高的100个数字.

任务完成.

Answer 4

我按顺序遍历列表.在我去的时候,我将元素添加到集合(或多重集,具体取决于重复).当集合达到100时,我只会在值大于集合中的最小值时插入(O(log m)).然后删除分钟.

调用列表中的值数n和要查找的值的数量m:

这是O(n*log m)

Answer 5

处理算法的速度绝对无关紧要(除非它完全是哑巴).

这里的瓶颈是I/O(指定它们在磁盘上).因此,请确保使用大缓冲区.