海量数据处理

[guodongxiaren]

面试中常见的海量数据处理题！

大小估算

bit、byte、KB、MB，GB是不是很容易乱！没这么麻烦。

• 快速估算，把1024模糊成1000。
• K、M、G就和西方数字表示法一样，三位数字一个逗号。其实就表示：千、百万、十亿！

比如3百万个int，那么就是3M个int。假设32位机器，一个int占4 字节（byte），那么三百万个int就是12M！

题外话

其实linux的sort、uniq等命令都支持塞不进内存的大文件处理。

[guodongxiaren]

大文件Top K

堆排序 内存中并不是放入所有数据，而是放入K大小的堆，我们知道堆调整的复杂度为lgK，使用K大小的堆，文件遍历一遍我们就可以求出前K大，所以复杂度是NlgK，N是词的个数，只不过这个“遍历”是文件操作，系数要比在内存中“遍历”的系数要大一些。求Top K大的数据用小根堆，求Top K小的数据用大根堆。

[guodongxiaren]

查找两个大文件中的相同元素

bitmap

[guodongxiaren]

大文件排序

外部排序 归并排序

方法一：

先根据大小分桶，遍历一遍拆成小文件。每个小文件内排序。有个问题是每个小文件的大小不好确定，可能分的粒度不够，导致小文件还是无法加载到内存中，还要再拆分排序合并。

[guodongxiaren]

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)。 遍历一遍小文件，统计每个文件中的数字个数。可以计算出中位数在哪个文件中，以及其中排第几的是中位数。 内存中加载那个文件，直接排序，可以找到中位数。

[guodongxiaren]

2.5亿个int找不重复数

bitmap 使用2-bitmap。00表示为出现，01表示出现1次，10表示出现2次或多次，11无意义。