大量数据处理问题

1、从大量URL中寻找重复URL

1Kb = 1000B
64B = 0.064Kb
50 = 5 * 64G = 320G内存
内存 8G 5G
1000 part
320M文件

存文件的一步进行处理
判断文件大小，
URL stream
hash(url) % 1000

并行在64文件里面找

go 一个协程负责接收然后对其进行 hash，看有没有这个hash文件，创建文件

2、在大量数据中寻找高频词

分治

遍历文件使用map统计频数

使用小顶堆遍历文件频数

求最大topN用小顶堆，求最小topN用大顶堆

3、在大量数据中找到不重复的数、或该数是否存在

方法一 分治

拆分文件，在文件中找到不重复的数，最后合并子集

方法二 位图

两个位图数组，取模取余进行落子。

4、从大量数据中找到中位数

数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 (N+1)/2 个数；当样本数为偶数时，中位数为 第 N/2 个数与第 1+N/2 个数的均值。

对于这道题，顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。

划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中，从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。