By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

一、分治/hash/排序

问题1、某日访问次数最多的IP

IP 是 32 位的，最多有个2^32个IP。

1、取模 1000，把整个大文件映射为 1000个小文件

2、再找出每个小文中出现频率最大的 IP

3、然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

问题2：有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词

1、顺序读文件中，对于每个词 x，取 hash(x) % 5000，然后按照该值存到 5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。

2、如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。

3、对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件

4、这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

问题3：给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中？

方案1：位图

申请 512 M的内存，一个 bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

方案2：折半查找

又因为 2^32 为 40 亿多，所以给定一个数可能在，也可能不在其中；

1、这里我们把 40 亿个数中的每一个用 32 位的二进制来表示，假设这 40 亿个数开始放在一个文件中。然后将这 40亿个数分成两类：第一种.最高位为 0，第二种：最高位为1

2、并将这两类分别写入到两个文件中，其中一个文件中数的个数 <= 20 亿，而另一个 >= 20 亿（这相当于折半了）；

3、与要查找的数的最高位比较并接着进入相应的文件再查找，再然后把这个文件为又分成两类: 第一种：次最高位为0，第二种：次最高位为1 ，并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）；

4、与要查找的数的次最高位比较并接着进入相应的文件再查找。以此类推，就可以找到了,而且时间复杂度为O(logn)

问题4：海量数据中找到中位数，内存肯定是无法一次性放下这么多数据的

中位数定义：数字排序之后，位于中间的那个数。比如将 100 亿个数字进行排序，排序之后，位于第 50 亿个位置的那个数就是中位数。

方案1：桶排序

1）创建多个小文件桶，设定每个桶的取值范围，然后把海量数据元素根据数值分配到对应的桶中，并记录桶中元素的个数

2）根据桶中元素的个数，计算出中位数所在的桶（比如 100 亿个数据，第 1 个桶到第 18 个桶一共有 49 亿个数据，第 19 个桶有 2 亿数据，那么中位数一定在第 19 个桶中），然后针对该桶进行排序，就可以求出海量数据中位数的值（如果内存还是不够，可以继续对这个桶进行拆分；或者直接用 BitMap 来排序）

方案2：折半查找，和问题3类似

1）假设这 100 亿数据都是 int 类型，4 字节（32 位）的有符号整数，存在一个超大文件中。

2）将每个数字用二进制表示，比较二进制的【最高位】 (第 32 位)，如果数字的最高位为 0，则将这个数字写入 file_0 文件中；如果最高位为 1，则将该数字写入 file_1 文件中。 最高位为符号位，也就是说 file_1 中的数都是负数，而 file_0 中的数都是正数。

3）通过这样的操作，这 100 亿个数字分成了两个文件，假设 file_0 文件中有 60 亿个数字，而 file_1 文件中有 40 亿个数字。

这样划分后，思考一下：所求的中位数在哪个文件中？

4）100 亿个数字的中位数是 100 亿个数排序之后的第 50 亿个数，现在 file_0 有 60 亿个正数，file_1 有 40 亿个负数，file_0 中的数都比 file_1 中的数要大，排序之后的第 50 亿个数是中位数，那么这个中位数一定位于 file_0 中，并且是 file_0 文件中所有数字排序之后的第 10 亿个数字。

现在，我们只需要处理 file_0 文件了（不需要再考虑 file_1 文件）。

5）而对于 file_0 文件，可以同样的采取上面的措施处理：将 file_0 文件依次读一部分到内存，将每个数字用二进制表示，比较二进制的【次高位】（第 31 位），如果数字的次高位为 0，写入 file_0_0 文件中；如果次高位为 1 ，写入 file_0_1 文件中。

6）现假设 file_0_0 文件中有 30 亿个数字，file_0_1 中也有 30 亿个数字，则中位数就是：file_0_0 文件中的数字从小到大排序之后的第 10 亿个数字。

7）抛弃 file_0_1 文件，继续对 file_0_0 文件 根据【次次高位】(第 30 位) 划分，如此反复下去

​

ContactAuthor