采访难题:使用有限的内存对百万数字输入进行排序

Question

我尝试使用外部排序来回答这个问题,但是访问者回答说复杂性是高nn(log(n)),即n square*logn.有没有更好的选择.

为了简化问题:让我们假设我们有1000个元素要排序,只为100个元素分配空间.什么是比外部排序花费更少时间的最佳算法.

Answer 1

我不知道你(或采访者)的意思,但是

我的建议是10路(在你的情况下)合并:

• 将文件拆分为MAX_MEM大小的块(100个元素)
  • 这是 O(1)
• 对内存中的每个块进行排序,并将其存储为单独的文件
  • 这是O((n/max_mem) * (max_mem) log(max_mem)))=O(n log(max_mem))
• 打开所有块作为元素流
• 通过选择每个步骤中的最低元素来合并所有流.
  • 这是O(n log(n/max_mem))使用minHeap或O(n^2/max_mem)平凡(在实践中可能更快)
• 删除块

关于计算,这是O(n (log(max_mem)+log(n/max_mem)))=O(n log(n))

关于磁盘I/O,如果所有的合并在一个一遍完成,这是2*n读取和2*n写入只.更一般地说,它是(1+[depth of the merge tree])*n

所有写入都是顺序的.第一个读取是顺序的,第二个读取是连续的,从10个文件交错.

如果有更多的数据,你需要重复或递归合并(每个块100个,然后重复选择N个块).此时,值得用@ amit的答案中的替换/选择替换split + sort步骤,特别是当数据已经几乎排序时(您可以完全避开合并步骤).

请注意,较高的N可能会增加计算(如果您使用正确的结构,则会非常轻微),但会显着减少磁盘I/O的数量(达到一定数量;如果您一次合并太多的块,则可能会耗尽读缓冲区的内存,导致不必要的读取).磁盘I/O很昂贵,CPU周期不是.