catbaron

海量数据处理总结

备战百度,在海量数据处理的主题上做一个总结。

详情来自http://www.cnblogs.com/pkuoliver/archive/2010/10/02/mass-data-topic-1.html


1.bloom filter

将数据通过hash函数映射到位数组,比如hash(str)=3则将位数组第三位置为1

对每一条数据都用k个hash函数进行映射,也就是一条数据会将位数组的最多k位的值置1


在查找数据是否存在的时候,则对其进行k次hash,如果位数组中对应的各位都被置1了,则说明该数据已经存在(明显是有一定错误率的)


bloom filter可以用来实现数据字典,进行数据的判重,或者集合求交集


同时,对其进行改进,即位数组每一位不再是0/1,而是数据出现的次数counter,那么出现数据则+1,删除数据则-1,这样可以实现删除操作。


实例:

给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。


2.hash表

hash表主要是整合了线性表”定位容易,添加删除复杂“和链表”添加删除容易定位复杂“的特点,将二者结合起来。线性表每一个元素位一个指针,指向一个链表。通过hash函数将一个数据映射到某个元素指向的链表上。如此查找是可以通过hash定位到链表,在链表中进行添加删除操作。


散列的方法有很多,不同的散列算法会导致链表的分布均衡问题。比较好的算法是非波那契算法


i ndex = (value * 理想乘数) >> 28


其中理想乘数为:

1,对于16位整数而言,这个乘数是40503

2,对于32位整数而言,这个乘数是2654435769

3,对于64位整数而言,这个乘数是11400714819323198485

适用

hash表适用于快速查找,但是需要数据可以全部放入内存。


作为扩展,可以使用d-left hashing

d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同 时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个 位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key 存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。


实例:

海量日志数据,提取出某日访问百度次数最多的那个IP。

IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。


3.Bit Map

类似遇bloom filter。若value==3,则将位数组第3位置1。这样,对于一串数字,进行如此造作后,从便利该位数组,若某位为1则输出下标,这样便完成了排序。

和插入排序很类似,但是其存储空间很小,适用于大量数据的排序,查重等操作。


实例

1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12.4MBytes,这样,就用了小小的12.4M左右的内存表示了所有的8位数的电话)

2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map,都是一样的道理。


4.堆

二叉堆是一种二叉树,最大堆为例,没一个节点都小于它的字节点。树是完全平衡的,并且最后一层的树叶都在最左边。


堆的操作主要是添加和删除。


适用

海量数据前n大,并且n比较小,堆可以放入内存


实例

最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元 素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。


5.双层桶思想

当数据量过大的时候,进行比较,查找处理较为复杂,因此可以考虑将大量数据操作划分位对很多小部分数据的操作。直接看例子:

实例

1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。 当然这个题也可以用我们前面讲过的BitMap方法解决,正所谓条条大道通罗马~~~


2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。


实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几 大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。


3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器,设计一个抽奖范围是0-350000彩票中奖号码列表,其中要包含20000个中奖号码。

这个题刚好和上面两个思想相反,一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12个区间,然后每个区间的长度都小于等于3万,这样我们就可以用题目给的随机数生成器来生成了,然后再加上该区间的基数。那么要每个区间生成多少个随机数呢?计算公式就是:区间长度*随机数密度,在本题目中就是30000*(20000/350000)。最后要注意一点,该题目是有隐含条件的:彩票,这意味着你生成的随机数里面不能有重复,这也是我为什么用双层桶划分思想的另外一个原因。


6.数据库索引


7.倒排索引

所谓倒排索引的意思,就是建立索引的时候,不是按照key-文档,value-语素这样的形式建立,而是按照key-语素,value-文档这种形式,而且在value中保存了文档编号和该文档中出现语素的次数等信息。


因此在检索的时候,不必遍历所有文档,而只需便利查找的query关键字即可。


评论

关注的博客