从大量整数中选取最小/大的若干个

问题描述：现在有非常大量的一堆对象，比如有几十亿甚至上百亿个。对象本身是什么可以忽略，每个对象都有唯一标识符和一个正整数属性值，属性值范围有限（不大于一亿）。在单核机器上，内存和磁盘空间充足，用什么方法可以最快地输出属性值最小的若干（如一万）个对象，要求输出结果按照属性值排序。

先说个题外话。前几天面试的时候，问了一个用栈模拟队列的题目，被candidate反问：这种问题在工作中会遇到么？有用么？

这个问题其实很好，值得我仔细思考。大体上来讲，我在面试的时候可能会这么几类问题（聊项目经验之类的除外）：

1. 某个编程语言的基础知识，如果candidate自称熟悉某语言；
2. 常见的数据结构，用来大概了解candidate的基本功；
3. 基本的编程题目，考察他的写代码能力；
4. 数学或算法问题，一方面了解candidate的基本功，另一方面看看他的思维能力和解决问题的能力；
5. 一些从实际工作中抽象出来的，相对而言比较开放的题目，主要是看他分析问题和解决问题的能力。

今天这个题目是我最近比较喜欢的一个问题，是曾经在工作中遇到过的。

先来看看题目中出现的数字带来什么信息。

• 对象的个数（设为n），十亿甚至百亿：也就是10^9到10^10这样的量级，已经接近甚至超过32位整数的范围。即使每个对象只占用1字节，总共也需要1G到10G的空间。
• 对象属性值的范围，正整数，一亿：相对于个数，属性值的范围还是相当有限的，最多有100M个各不相同的值，可以用32位整数表示。
• 要求选取的对象个数（设为m），一万左右：相对于个数来说是非常非常小的。

可见，单单保存所有的属性值也需要4G到40G的空间。标识符最少也得用64位整数表示，又需要8G到80G的空间。

在这种特殊的要求下，怎么处理是最高效的呢？来看看以下的几种方法。

方法一：快速选择/线性选择算法

快速选择和线性选择算法都是平均时间复杂度O(n)的选择算法，当然线性选择算法在最坏情况下也能保证O(n)时间，缺点是实现起来比较复杂。简单起见，我就用快速选择算法。

快速选择算法类似于快速排序，用一个轴值将数组分成两部分，一部分全都比轴值小，而另一部分全都比轴值大。然后看看两部分分别包含多少个元素，从而确定第m大的元素应该再哪一半，然后对那一半递归处理，直到找到第m大的元素。

但是将快速选择算法应用到本题时，遇到主要问题是内存恐怕不够。

如果在内存中放入所有的对象，我们需要12G到120G内存，取决于对象的个数是十亿还是一百亿。进入内存后，还需要至少两次遍历才可以找到第m大的元素。另外加载数据时需要有一次完整的文件遍历。

如果内存中无法放入所有的对象，那就比较麻烦了，在头几次二分递归的时候可能需要动用硬盘来缓存数据，磁盘IO将成为可怕的瓶颈。累加起来相当于至少两次全文件的读遍历和写遍历。实际上，在确定了第m大的对象后，可能还需要遍历一次整个文件，找出比它小的对象。

方法二：堆排序算法

堆排序也是一个很好的可以用于部分排序的算法，C++ STL就用堆排序来实现partial_sort。

在内存中维护一个大小为m的最大值堆（没错，是最大值堆），遍历整个文件，每拿到一个对象，拿它与堆顶的属性值比较一下，如果新对象的属性值大就直接丢弃，否则用它取代堆顶元素。平均来讲，这样处理的时间复杂度是n * log m。

方法三：哈希算法

我们注意到，虽然对象的个数非常大，但属性值的范围非常小（相对来讲）。如果在值域范围上建立一个哈希表，只需要100M个格子，如果一个格子存储一个32位整数，只需要400M内存。

哈希表总是会有冲突的，在这个问题中，冲突是必然的，平均每个属性值上会有10到100个不同的对象。但处理冲突的办法非常简单，因为我们不需要在哈希表中记录每个对象，只需要记录这个属性值对应的对象的个数。

开辟一个能存放100M个32位整数的数组（为保险起见，可以用64位整数，但总共也只需要800M内存），数组的下标对应于属性值（实际操作中可能要减一）。然后遍历整个文件，每拿到一个对象，将对应的数组元素值加一。

文件遍历完后，过一下这个数组，可以找出第m大的对象的属性值，这个值就是一个边界。然后再遍历一次原始文件，把属性值小于等于边界的对象都放到内存中（注意在相等时，会有个数的限制）。最后把内存中的m个对象按照属性值排一下序再输出即可。

这样最多只需要遍历两次文件，使用O(n)时间就可以完成题目的要求。

到底哪个方法快？

上面提到了三种算法，到底哪一个最快呢？说说你的看法吧？

我以前一直觉得哈希法是最快的，它对内存的需求量适中，算法是线性时间。但后来又仔细想了想，觉得不太对。这里实际上不完全是内存中的运算了，瓶颈主要是在磁盘IO上。

让我们来比较一下三种算法：

1. 快速选择算法（所有对象可以全进内存）：只需要一次文件读遍历，内存操作是O(n)时间（系数至少为2，可能会很大）。
2. 快速选择算法（只有部分对象可进内存）：平均需要三次文件读遍历，两次写遍历，内存操作是O(n)时间（系数至少为2，可能会很大）。
3. 堆排序算法：需要一次文件读遍历，内存操作是O(n * log m)时间，这里m取10000的话，大概是13。当然实际数值会少于13，因为并不是每个对象都需要进入堆中。
4. 哈希算法（所有对象可以全进内存）：需要一次文件读遍历，在内存中要开辟大小为O(n)和O(m)的两块缓冲区，内存操作时间为O(n)（系数大约为2）。
5. 哈希算法（只有部分对象可进内存）：需要两次文件读遍历，内存操作是O(n)时间（系数小于2）。

题目的本意就是几乎不可能让所有对象都进入内存。虽然堆排序的内存操作时间复杂度偏高，却只需要一次磁盘遍历操作，其消耗的时间应该要小于哈希算法的。你是否同意呢？

最近做了个实验，生成了十亿个对象，每个对象有一个64位整数作为标识符，还有一个不超过一亿的随机整数作为属性值。生成的文件用文本格式存储，占用18G磁盘空间。我没有实验快速选择算法，只是比较了堆排序和哈希。实验结果是：

• 单纯遍历一次文件，包括逐行读取，把属性值解析成整数：耗时34分钟；
• 堆排序算法：耗时40分钟；
• 哈希算法：耗时73分钟。

这三个时间的相对值是否在你的预料之中呢？

当然，如果把硬盘换成SSD恐怕结果又完全不同了，有兴趣的童鞋可以试一试。

转载自 http://www.gocalf.com/blog/topn-of-massive-data.html