文章目录
- 一、计算容量
- 二、拆分
- 三、解决思路之分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序
- 1、海量日志数据，提取出某日访问百度次数最多的那个IP
- 2、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
- 3、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
- 四、解决思路之Bitmap/布隆过滤器
- 1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
- 五、解决思路之外排序
- 1、如何排序10亿个数
- 六、海量数据找中位数
一、计算容量
二、拆分
可以将海量数据拆分到多台机器上和拆分到多个文件上：
- 如果数据量很大，无法放在一台机器上，就将数据拆分到多台机器上。这种方式可以让多台机器一起合作，从而使得问题的求解更加快速。但是也会导致系统更加复杂，而且需要考虑系统故障等问题；
- 如果在程序运行时无法直接加载一个大文件到内存中，就将大文件拆分成小文件，分别对每个小文件进行求解。
按散列值拆分：选取数据的主键 key，然后通过哈希取模 hash(key)%N 得到该数据应该拆分到的机器编号，其中 N 是机器的数量。优点是不需要使用查找表，缺点是可能会导致一台机器存储的数据过多，甚至超出它的最大容量。
三、解决思路之分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序
1、海量日志数据，提取出某日访问百度次数最多的那个IP
既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：
- 分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决；
- hash统计：当大文件转化了小文件，那么我们便可以采用常规的unodered_map(ip，value)来进行频率统计。
- 堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。
2、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
由上面那两个例题，分而治之 + hash统计 + 堆/快速排序这个套路，我们已经开始有了屡试不爽的感觉。下面，再拿几道再多多验证下。请看此第3题：又是文件很大，又是内存受限，咋办?还能怎么办呢?无非还是：
- 分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
- hash统计：对每个小文件，采用trie树/unodered_map等统计每个文件中出现的词以及相应的频率。
- 堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。
3、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
- 遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,…,a999，每个小文件约300M)；
- 遍历文件b，采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,…,b999)；这样处理后，所有可能相同的url都被保存在对应的小文(a0vsb0,a1vsb1,…,a999vsb999)中，不对应的小文件不可能有相同的url。然后我们只要求出这个1000对小文件中相同的url即可。
- 求每对小文件ai和bi中相同的url时，可以把ai的url存储到hash_set中。然后遍历bi的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
四、解决思路之Bitmap/布隆过滤器
所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。可进行数据的快速查找，判重，删除。
如果说Bitmap对于每一个可能的整型值，通过直接寻址的方式进行映射，相当于使用了一个哈希函数，那布隆过滤器就是引入了k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程。下图中是k=3时的布隆过滤器。但是布隆过滤器会误判，也就是将一个不存在的数判断为已经存在，这会造成一定的问题。
1、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
五、解决思路之外排序
1、如何排序10亿个数
10亿个32位整数需要4G左右的内存，一次性载入内存是不现实的，必须要采用外排。
外排序一般是应对于数据量非常大的数据，这些数据放在硬盘上，无法一次性的放到内存上。所以，我们通常采用的思路对于这些数据就是进行切分，然后对切分出来的文件进行排序。在排序的时候，小文件我们采用快排来排序，如果是大文件，我们就从两个文件中一个一个读取，然后进行归并排序，放入合并以后的文件当中，最后最大的文件就是排序以后的结果。
六、海量数据找中位数
现在有10亿个int型的数字，以及一台可用内存为1GB的机器，如何找出这10亿个数字的中位数？
采用基于二进制位比较和快速排序算法中的“分割思想”来寻找中位数。
假设10亿个数字保存在一个大文件中，依次读一部分文件到内存(不超过内存的限制：1GB)，将每个数字用二进制表示，比较二进制的最高位(第32位)，如果数字的最高位为0，则将这个数字写入 file_0文件中；如果最高位为 1，则将该数字写入file_1文件中。【这里的最高位类似于快速排序中的枢轴元素】。
从而将10亿个数字分成了两个文件（几乎是二分的），假设 file_0文件中有 6亿 个数字，file_1文件中有 4亿 个数字。那么中位数就在 file_0 文件中，并且是 file_0 文件中所有数字排序之后的第 1亿 个数字。
【为什么呢？因为10亿个数字的中位数是10亿个数排序之后的第5亿个数。现在file_0有6亿个数，file_1有4亿个数，file_0中的数都比file_1中的数要大（最高位为符号位，file_1中的数都是负数，file_0中的数都是正数，也即这里一共只有4亿个负数，排序之后的第5亿个数一定是正数，那么排序之后的第5亿个数一定位于file_0中）】。除去4亿个负数，中位数就是6亿个正数从小到大排序之后 的第 1 亿个数。
现在，我们只需要处理 file_0 文件了（不需要再考虑file_1文件）。对于 file_0 文件，同样采取上面的措施处理：将file_0文件依次读一部分到内存(不超内存限制：1GB)，将每个数字用二进制表示，比较二进制的次高位（第31位），如果数字的次高位为0，写入file_0_0文件中；如果次高位为1，写入file_0_1文件 中。现假设 file_0_0文件中有3亿个数字，file_0_1中也有3亿个数字，则中位数就是：file_0_0文件中的数字从小到大排序之后的第1亿个数字。以此类推，直到可以放入内存排序为止。
