大数据量,海量数据处理方法总结[转][文].pdf资源-CSDN文库

版权申诉

11 浏览量 2021-10-12 03:30:48 上传评论收藏 19KB PDF 举报

资源推荐

资源详情

资源评论

[ 转] 大数据量，海量数据处理方法总结

大数据量的问题是很多面试笔试中经常出现的问题，比如 baidu google 腾讯这样的一些

涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能

完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一

些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，

欢迎与我讨论。

1.Bloom filter

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：

对于原理来说很简单，位数组 +k 个独立 hash 函数。将 hash 函数对应的值的位数组置 1 ，

查找时如果发现所有 hash 函数对应位都是 1 说明存在，很明显这个过程并不保证查找的结

果是 100% 正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会

牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter ，用一个 counter

数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何根据输入元素个数 n ，确定位数组 m 的大小及 hash 函数

个数。当 hash 函数个数 k=(ln2)*(m/n) 时错误率最小。在错误率不大于 E 的情况下， m

至少要等于 n*lg(1/E) 才能表示任意 n 个元素的集合。但 m 还应该更大些，因为还要保证

bit 数组里至少一半为 0，则 m 应该 >=nlg(1/E)*lge 大概就是 nlg(1/E)1.44 倍 (lg 表示

以 2 为底的对数 ) 。

举个例子我们假设错误率为 0.01 ，则此时 m 应大概是 n 的 13 倍。这样 k 大概是 8 个。

注意这里 m 与 n 的单位不同， m 是 bit 为单位，而 n 则是以元素个数为单位 ( 准确的说是

不同元素的个数 ) 。通常单个元素的长度都是有很多 bit 的。所以使用 bloom filter 内存上

通常都是节省的。

扩展：

Bloom filter 将集合中的元素映射到位数组中，用 k（ k 为哈希函数个数）个映射位是否全

1 表示元素在不在这个集合中。 Counting bloom filter （CBF ）将位数组中的每一位扩展

为一个 counter ，从而支持了元素的删除操作。 Spectral Bloom Filter （SBF ）将其与集

合元素的出现次数关联。 SBF 采用 counter 中的最小值来近似表示元素的出现频率。

问题实例：给你 A,B 两个文件，各存放 50 亿条 URL ，每条 URL 占用 64 字节，内存限制

是 4G ，让你找出 A,B 文件共同的 URL 。如果是三个乃至 n 个文件呢？

根据这个问题我们来计算下内存的占用， 4G=2^32 大概是 40 亿*8 大概是 340 亿，n=50

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

内容反馈

版权申诉

czq131452007

粉丝: 2
资源: 12万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip