前言

Github:https://github.com/HealerJean

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

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

IP32 位的,最多有个2^32IP

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:位图

申请512M的内存,一个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)

ContactAuthor