小灰学习大数据——大数据算法探索(1)

原创
2017/01/08 19:36
阅读数 255

  小灰学习大数据主要是针对大数据的面试题和笔试题分析,学习来写的。希望能让自己有提示,也能帮助别人。废话不多说,上题了。

  • 问:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

​​​​​​​  首先看到题目开始分析,50亿个url,一个64字节是多大呢?

我们先来计算,64/1024=0.0625bit一个url.     0.0625*50亿约等于320G.这么看挺大的所以不可能将其完全加载到内存中处理,考虑采取分而治之的方法。好有这个思路,我们提出以下方案。

方案1:将大文件分成能够被内存加载的小文件。

前面分析每个文件的大小为50G×64=320G,远远大于内存限制的4G。所以

s 遍历文件a,对每个url求取 ,然后根据所取得的值将url分别存储到1000个小文件(记为 )中。这样每个小文件的大约为300M。

s 遍历文件b,采取和a相同的方式将url分别存储到1000各小文件。这样处理后,所有可能相同的url都在对应的小文件中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

s 求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

方案2:内存映射成BIT最小存储单元。(网上看的,所以我准备弄懂它)

如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

  首先,我们来看看什么事Bloom filter?

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

上过数据结构我们知道,单一哈希函数发生冲突的概率太高。Hash表冲突的各种解决方法,若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。所以我们用Bit-Map方法,建立一个BitSet,将每个URL经过多个哈希函数映射到某一位。下面来看看具体做法

  1. 创建一个m位BitSet,先将所有位初始化为0,然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1

                       图1.Bloom Filter加入字符串过

 

    

  •    2.检查该bitset字符串是否存在

  对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。然后检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位是否为1,若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1,则“认为”字符串str存在; 若一个字符串对应的Bit不全为1,则可以肯定该字符串一定没有被Bloom Filter记录过。(这是显然的,因为字符串被记录过,其对应的二进制位肯定全部被设为1了)

  但是若一个字符串对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的。(因为有可能该字符串的所有位都刚好是被其他字符串所对应)这种将该字符串划分错的情况,称为false positive 。

  • 3.哈希表和表长参数选择

    (1)哈希函数选择

         哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。

       (2)Bit数组大小选择 

         哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考文献1。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。

参考文献1:http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

 

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部