海量数据处理
Opened this issue · 5 comments
面试中常见的海量数据处理题！
大小估算
bit、byte、KB、MB，GB是不是很容易乱！没这么麻烦。
- 快速估算，把1024模糊成1000。
- K、M、G就和西方数字表示法一样，三位数字一个逗号。其实就表示：千、百万、十亿！
比如3百万个int，那么就是3M个int。假设32位机器，一个int占4 字节（byte），那么三百万个int就是12M！
题外话
其实linux的sort、uniq等命令都支持塞不进内存的大文件处理。
大文件Top K
堆排序
内存中并不是放入所有数据，而是放入K大小的堆，我们知道堆调整的复杂度为lgK，使用K大小的堆，文件遍历一遍我们就可以求出前K大，所以复杂度是NlgK，N是词的个数，只不过这个“遍历”是文件操作，系数要比在内存中“遍历”的系数要大一些。求Top K大的数据用小根堆，求Top K小的数据用大根堆。
查找两个大文件中的相同元素
bitmap
大文件排序
外部排序 归并排序
方法一：
先根据大小分桶，遍历一遍拆成小文件。每个小文件内排序。有个问题是每个小文件的大小不好确定，可能分的粒度不够，导致小文件还是无法加载到内存中，还要再拆分排序合并。
5亿个int找它们的中位数
分桶法
把5亿个int一次性放入内存，需要空间2GB：500000000*4B/1000/1000/1000=2
这个估算过程太蠢了。记住10亿是1G，1G个int（一个int占4B），那么总内存就是4G。5亿int就是2G内存！快不快。
其实存的下……才2G。但看意思就是海量数据题，不要和面试官较真了，否则他会换成100亿。
遍历一遍数字文件，按照数字大小拆分到50个小文件中，每个文件存储1000W个数(每个文件40M)。
遍历一遍小文件，统计每个文件中的数字个数。可以计算出中位数在哪个文件中，以及其中排第几的是中位数。
内存中加载那个文件，直接排序，可以找到中位数。
2.5亿个int找不重复数
bitmap
使用2-bitmap。00表示为出现，01表示出现1次，10表示出现2次或多次，11无意义。