海量数据题我之前整理过一部分，这里就直接贴出来了，抛砖引玉。
常见解题思路：
- 分治：
hash后单独处理，最后合并
- 布隆过滤器
- 位图法
- 最大/最小堆
1. 海量日志数据，提取出某日访问百度次数最多的那个IP
首先我们要了解
IP长啥样：255.255.255.255，我们又知道2^8 = 256，所以这里需要4个8 bit，也就是4 * 8 = 32 bit，每个bit有两种可能，所以一共有2^32种IP，我们拆分成1024个文件：2^10 = 1024
2^32 / 2^10 = 2^22 = 2^2 * 2^20 = 4M也就是说每个文件的大小为
4M，接下来我们遍历日志文件，把每个IP采用哈希方式映射到1-1024个文件中，那么相同IP就会到达同一个文件中，然后对每个文件求IP的最大重复数，最后对1024个文件的各个最大值再求一次最大值，得到最终结果。类似题目：
- 在海量数据中找出重复次数最多的一个
2. 32位的机器，2亿个整数中找不重复数字？
首先我们理清楚题意，说白了就是两亿个
int整数，我们必然是要遍历这2亿个整数的，这个过程中会出现三种状态：未出现、出现、重复出现，既然是三种状态，1位不够用，我们用2位来存，00代表未出现，01代表出现一次，10代表多次重复出现，我们首先遍历2亿个整数，然后出现的整数就把对应位置改为01，如果当前状态已经是01，则改为10，那么这样遍历一遍之后，我们就再遍历一遍用来存储的数据，根据状态就知道哪些是不重复数字了。3. 如何快速判断某个数是否在40亿个整数当中？
完整题目大致如下：给
40亿个不重复的unsigned int的整数，没有排序，然后再给一个数，判断是否存在。这题就是很明显的布隆过滤器了，与前一题不同的是，我们可以不需要用两位来表示一个整数，毕竟这里只需要存在和不存在两个情况，
1 bit就足够了，所以我们可以用类似上面的思路，先遍历40 亿个整数，出现了，则将相应位置的bit修改为1，判断的时候也只需判断对应位置的bit是0还是1。0则代表不存在，1则代表存在。4. 取超大文件数字交集
现有两个各有
20亿行的文件，每一行都只有一个数字，求这两个文件的交集。因为
int的范围长度是2^32 == 4G ≈ 40亿，用一个bit来表示一个int值，大概需要4G个bit位，即约4G/8 = 552M的内存。这可以解决问题了- 如果都是正数：
用
unsigned int存的话，4G bit / 32b = 2^32 / 2^5 = 2^27 = 2^7 * 2^20 = 128M个建立
unsigned int [128M] 的数组，对于每个数，先 /32，确定在数组哪个位置，然后%32，确定在该unsigned int的哪一位，然后对这两个数组取并集即可。- 如果有正负数：
那么其实只要把负数的绝对值存下来即可和正数使用同样的方法，因此我们需要两对数组，一对存各自的正数，另一对则存负数的绝对值。
类似题目：
给两个存放
url的文件，各20亿条，求交集；题目类似，但思路却不一样，我们使用分治 +
hash，把分别把两个文件使用hash的方式切割成1024个文件，2^10 = 1024 ≈ 10^3，所以20亿 = 2 * 10^9 ≈ 2 * 2^30 = 2^31，那么切割成1024个文件后，每个文件大小约为2 M，那么求交集很好操作了，我们把A文件切割的a1、a2...与B文件切割的b1、b2...文件一一对应去求交集。可以这么做的原因在于hash会把相同的url映射到同一位置的文件上。5. 2G内存，10G大小的数字，求中位数
- 双堆法
用大顶堆放较小的数，小顶堆放较大的数；如果两者数量差距大于一，那么把多的那堆的堆顶弹出，加入到另一堆中；最终多的一堆的堆顶就是中位数，如果数量相同，则取两个堆顶求平均值。
- 分治法
根据二进制首位是
0还是1进行划分，然后比较两堆里面哪个多哪个少，中位数一定在多的里面；继续递归第二位是0还是1，直到剩下一个数，或者剩下两个数求平均。参考链接
Loading Comments...