Cracking the coding interview--Q9.4

January 19, 2013
作者:Hawstein
出处:http://hawstein.com/posts/9.4.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

译文:

如果你有个2GB的文件,其中每一行是一个字符串,你会使用哪种算法来排序,为什么?

解答

当面试官说到2GB文件的时候,他其实就是在暗示你, 他并不希望一次性把所有的数据都载入内存。这样子的话,我们要怎么做呢? 我们每次就将部分数据载入内存就好了。

算法:

首先我们要了解,可以用的内存有多大?假设我们有X MB的内存可用。

  1. 我们将文件分为K份,其中X*K=2GB。每次取其中一份载入到内存中, 用O(nlog n)的算法排序,然后再保存到外部文件。
  2. 载入下一份并排序
  3. 当我们将K份小文件都排好序,合并它们。

上面的算法就是外排序,步骤3又称为N路归并。

使用外排序是由于数据太大了,无法一次全部加载到内存中,所以需要借助磁盘进行存储, 每次只从磁盘中加载一部分数据进入内存,进行排序。

推荐阅读: 维基百科:外排序

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview