按query频度排序的方法

【出自BD面试题】

难度系数：★★★★☆ 被考察系数：★★★★★

题目描述：

有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求按照query的频度排序。

分析与解答：

对于这种题，如果query的重复度比较大，那么可以考虑一次性把所有query读入到内存中处理，如果query的重复率不高，那么可用的内存不足以容纳所有的query，那么就需要使用分治法或者其他的方法来解决。

方法一：hash_map法(www.xing528.com)

如果query的重复率比较高，说明不同的query总数比较小，可以考虑把所有的query都加载到内存中的hash_map中（由于hash_map中针对每个不同的query只保存一个键值对，因此这些query占用的空间会远小于10GB，有希望把它们一次性都加载到内存中）。接着就可以对hash_map按照query出现的次数进行排序。

方法二：分治法

这种方法需要根据数据量的大小以及可用内存的大小来确定问题划分的规模。对于本题而言，可以顺序遍历10个文件中的query，通过Hash函数hash（query）%10把这些query划分到10个文件中，通过这样的划分，每个文件的大小为1GB左右，当然可以根据实际情况来调整hash函数，如果可用内存很小，可以把这些query划分到更多的小的文件中。

如果划分后的文件还是比较大，可以使用相同的方法继续划分，直到每个文件都可以被读取到内存中进行处理为止，然后对每个划分后的小文件使用hash_map统计每个query出现的次数，然后根据出现次数排序，并把排序好的query以及出现次数写入到另外一个单独的文件中。这样针对每个文件，都可以得到一个按照query出现次数排序的文件。

接着对所有的文件按照query的出现次数进行排序，这里可以使用归并排序（由于无法把所有的query都读入到内存中，因此这里需要使用外排序）。