> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/other-algorithms-and-data-structure/external-sorting.md). # External Sorting **Source**: Jiuzhang's Tutorial: 所谓的外排序算法（External Sorting），是指在`内存不够的情况下`，如何对存储在一个或者多个大文件中的数据进行排序的算法。 参考资料： * [CNBLOG](http://www.cnblogs.com/LUO77/p/5838206.html) * [GeeksForGeeks](https://www.geeksforgeeks.org/external-sorting/) * [WIKI](https://en.wikipedia.org/wiki/External_sorting) 外排序算法通常是解决一些大数据处理问题的第一个步骤，或者是面试官所会考察的算法基本功。 ## 外排序算法的基本步骤 外排序算法分为两个基本步骤： 1. 将大文件切分为若干个个小文件，并分别使用内存排好序 2. 使用`K路归并算法`将若干个排好序的小文件合并到一个大文件中 #### 第一步：文件拆分 根据内存的大小，尽可能多的分批次的将数据 Load 到内存中，并使用系统自带的内存排序函数（或者自己写个快速排序算法），将其排好序，并输出到一个个小文件中。比如一个文件有1T，内存有1G，那么我们就这个大文件中的内容按照 1G 的大小，分批次的导入内存，排序之后输出得到 1024 个 1G 的小文件。 #### 第二步：K路归并算法 K路归并算法使用的是数据结构堆（Heap）来完成的，使用 Java 或者 C++ 的同学可以直接用语言自带的 PriorityQueue（C++中叫priority\_queue）来代替。 我们将 K 个文件中的第一个元素加入到堆里，假设数据是从小到大排序的话，那么这个堆是一个最小堆（Min Heap）。每次从堆中选出最小的元素，输出到目标结果文件中，然后如果这个元素来自第 x 个文件，则从第 x 个文件中继续读入一个新的数进来放到堆里，并重复上述操作，直到所有元素都被输出到目标结果文件中。 **Follow up: 一个个从文件中读入数据，一个个输出到目标文件中操作很慢，如何优化？** 如果我们每个文件只读入1个元素并放入堆里的话，总共只用到了 1024 个元素，这很小，没有充分的利用好内存。另外，单个读入和单个输出的方式也不是磁盘的高效使用方式。因此我们可以为输入和输出都分别加入一个缓冲（Buffer）。假如一个元素有10个字节大小的话，1024 个元素一共 10K，1G的内存可以支持约 100K 组这样的数据，那么我们就为每个文件设置一个 100K 大小的 Buffer，每次需要从某个文件中读数据，都将这个 Buffer 装满。当然 Buffer 中的数据都用完的时候，再批量的从文件中读入。输出同理，设置一个 Buffer 来避免单个输出带来的效率缓慢。 ## 面试题 ### 求两个超大文件中 URLs 的交集 #### 问题描述 给定A、B两个文件，各存放50亿个URLs，每个 URL 各占 64 字节，内存限制是 4G，让你找出A、B文件共同的 URLs？ #### 问题分析 首先需要跟面试官澄清一个问题： > 这两个文件各自是否已经没有重复？ 通常面试官会先让你假设没有重复，然后再来看有重复的情况怎么处理。那我们就先来看没有重复的情况。 #### A,B各自没有重复 URLs **方法1：文件拆分 Sharding（也可以叫 Partitioning）**\ 50亿，每个 URLs 64 字节，也就是每个文件 320G 的大小。很显然我们不能直接全部 Load 到内存中去处理。这种内存不够的问题，通常我们的解决方法都可以是使用 hash function 来将大文件拆分为若干个小文件。比如按照`hashfunc(url) % 200`进行拆分的话，可以拆分成为，200 个小文件 —— 也就是如果 hashfunc(url) % 200 = 1 就把这个 url 放到 1 号文件里。每个小文件理想状况下，大小约是 1.6 G，完全可以 Load 到内存里。 这种方法的好处在于，因为我们的目标是要去重，那么那些A和B中重复的 URLs，会被`hashfunc(url) % 200`映射到同一个文件中。这样在这个小文件中，来自 A 和 B 的 URls 在理想状况下一共 3.2G，可以全部导入内存进入重复判断筛选出有重复的 URLs。 **Q: 刚才一直在说理想情况下，那么不理想情况下是什么样的？该怎么处理？** A: 不理想的情况下，如果 hashfunc(url) % 200 的结果比较集中，那么有可能会造成不同的 URLs 在同一个文件中扎堆的情况。这种情况下，有一些文件的大小可能会超过 4G。对于这种情况，处理的办法是进行二次拆分，把这些仍然比较大的小文件，用一个新的 hashfunc 进行拆分：`hashfunc'(url) % X`。这里再拆成多少个文件，可以根据文件的实际大小来定。如果二次拆分之后还是存在很大的文件，就进行三次拆分。直到每个小文件都小于 4G。 **方法2：BloomFilter**\ 我们可以使用一个 4G 的 Bloom Filter，它大概包含 320 亿 个 bit。把 A 文件的 50亿 个 URLs 丢入 BF 中，然后查询 B 文件的 每个 URL 是否在 BF 里。这种方法的缺点在于，320 亿个 bit 的 BF 里存 50 亿个 URLs 实在是太满了（要考虑到BF可能会用4个哈希函数），错误率会很高。因此仍然还需需要方法1中的文件拆分来分批处理。 **方法3：外排序算法** 将A,B文件分别拆分为80个小文件，每个小文件4G。每个文件在拆分的时候，每4G的数据在内存中做快速排序并将有序的URLs输出到小文件中。 用多路归并算法，将这160个小文件进行归并，在归并的过程中，即可知道哪些是重复的 URLs。只需将重复的 URLs 记录下来即可。 #### Follow up: A,B各自有重复的 URLs 当 A, B 各自有重复的 URLs 的时候，比如最坏情况下，A里的50亿个URLs 全部一样。B里也是。这样采用方法1这种比较容易想到的 Sharding 方法，是不奏效的，因为所有 URLs 的 hashcode 都一样，就算换不同的 hashfunc 也一样。这种情况下，需要先对两个文件进行单独的去重，方法是每 4G 的数据，放到内存中用简单的哈希表进行去重。这样，在最坏情况下，总共 320G 的数据里，一个 URLs 最多重复 8次，则不会出现太严重的扎堆情况了。算法上唯一需要稍微改动的地方是，由于 A 存在多个重复的 URLs，所以当和 B 的 URLs 被sharding 到同一个文件里的时候，需要标记一下这个 URLs 来自哪个文件，这样才能知道是否在A和B中同时出现过。 另外，使用外排序的方法，是无需对两个文件进行单独去重的步骤的。