几道大数据处理题（转）

 

1. 给A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。

 

分析：

1MB = 2^20 = 10^6 = 100万

1GB = 2^30 = 10^9 = 1亿

 

50亿url = 5G*64 Byte

 

整理方法如下：

方法一：

分别扫描A,B文件，根据hash(url)%k值将url划分到不同的k个文件中，如a1，a2,....ak;b1，b2，...bk，（保存时可以把hash值也保存进去，避免以后重复计算) 对每一个hash段的两个文件，如a1，b1, 读取a1到一个HashSet中，再将b1投入，用链表保持hash值有冲突且url相等的url。

 

分割的文件数k: k> 5G*64/4G/2 = 160

当然该方法需要更多的磁盘空间

 

方法二：

使用Bloom filter。假设布隆过滤器的错误率为0.01，则位数组大小m约为输入元素个数n的13倍，此时需要的哈希函数k约为8个。（Google黑板报中介绍其用来存储垃圾邮件地址）

 

n = 5G

m = 5G * 13 = 65G = 650亿 即需要650亿个bit位才能达到错误率0.01

而我们拥有的内存可容纳bit位个数：4G * 8bit = 32G bit = 320亿，按此实现错误率大于0.01。

 

方法三：

使用索引。想想，可以讲A存入数据库表并建立主键和索引，再将B读入插入数据库表，若报错则是重复的url。

 

 

2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序.

 

方法一：类似第1题方法一，扫描所有文件，使用hash将query重新散到不同文件中，这样相同的query一定在同一个文件中。

对每个小文件进行计数。最后归并结果。

 

方法二：类似第1题方法二，但用的是Bloom Filter的变化SBF（Spectral Bloom Filter）

 

Bloom Filter的变种:

CBF（Counting Bloom Filter）通常采用固定的4bit的counter来记录出现频次，可以保证极小溢出概率，CBF使用counter只为了实现元素删除。

SBF（Spectral Bloom Filter）若想要支持元素的出现频率查询，4位远远不够，这就需要动态大小的counter

 

 

Bloom Filter介绍：

Bloom Filter概念和原理 

Counting Bloom Filter 

Spectral Bloom Filter

 

方法三：使用MapReduce。

 

3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。

 

方法：扫描文件hash成小文件。各个文件分别计数，取前100个词。

最后合并各文件找出最终的100词。或将所有小文件的前100词投入大小为100的最小堆