从另一个角度看大数据量处理利器:布隆过滤器

  思路:从简单的排序谈到BitMap算法,再谈到数据去重问题,谈到大数据量处理利器:布隆过滤器。

情景1:对无重复的数据进行排序

@给定数据(2,4,1,12,9,7,6)如何对它排序?

     方法1:基本的排序方法包括冒泡,快排等。

     方法2:使用BitMap算法

     方法1就不介绍了,方法2中所谓的BitMap是一个位数组,跟平时使用的数组的唯一差别在于操作的是位。

首先是开辟2个字节大小的位数组,长度为16(该长度由上述数据中最大的数字12决定的)如图



 
      然后,读取数据,2存放在位数组中下标为1的地方,值从0改为1,4存放在下标为3的地方,值从0改为1....结果如图


   

      最后,读取该位数组,得到排好序的数据是:(1,2,4,6,7,9,12)


      比较方法1和方法2的差别:方法2中,排序需要的时间复杂度和空间复杂度很依赖与数据中最大的数字比如12,因此空间上讲需要开2个字节大小的内存,时间上需要遍历完整个数组。当数据类似(1,1000,10万)只有3个数据的时候,显然用方法2,时间复杂度和空间复杂度相当大,但是当数据比较密集时该方法就会显示出来优势。

情景2:对有重复的数据进行判重

   数据(2,4,1,12,2,9,7,6,1,4)如何找出重复出现的数字?

       首先是开辟2个字节大小的位数组,长度为16(该长度由上述数据中最大的数字12决定的)如图


   

      当读取完12后,数组中的数据如下图:


      当读取2的时候,发现数组中的值是1,则判断出2是重复出现的。

应用

      应用1:某文件中包含一些8位的电话号码,统计出现的号码的个数?(判断有谁出现)

      8为最大是99 999 999,大约是99M的bit,12.5MB的内存,就可以统计出来出现的号码。

 

      应用2某文件中包含一些8位的电话号码,统计只出现一次的号码?(判断有谁出现并且指出现1次)

      需要扩展一下,可以用两个bit表示一个号码,0代表没有出现过,1代表只出现过1次,2代表至少出现2次。 

 

      应用3:有两个文件,文件1中有1亿个10位的qq号码,文件2中有5千万个10位qq号码,判断两个文件中重复出现的qq号。

     首先建立10的10次方个大小的位数组(占用内存大约是1.25G),全部初始化为0,读取第一个文件,对应的qq号存放到对应的未知,数值改为1,如果重复出现仍是1.读取完毕第一个文件后,读取第二个文件,对应的位置为1则表示重复出现。

 

     应用4:有两个文件,文件1中有1亿个15位的qq号码,文件2中有5千万个15位的qq号码,判断两个文件中重复出现的qq号。 


    应用4中,qq号码上升为15位的时候,显然内存是不够用了,这个时候怎么办?使用Bloom Filter(布隆过滤器)

 

Bloom Filter(布隆过滤器):

      对于Bit-Map分析一下,每次都会开辟一块表示最大数值大小的bit数组,比如情景1中的16,将对应的数据经过映射到bit数组的下标,这其实是一种最简单的hash算法,对1去模。在上述应用4中,当qq号码改为15位的时候,Bit-Map就不太好用了,如何改进呢?解决办法:减少bit数组的长度,但是增加hash函数的个数

对于每一个qq号码,我用K个hash函数,经过k次映射,得到k个不同位置,假设k=3,那么对于一个qq号码,映射到位数组中3个不同的位置


 

当读取第二个包含5千万个qq号码的文件的时候,使用同样的3个hash函数进行映射,当3个位置全部是1的时候才表示出现过,否则表示没有出现过。

有什么疑问吗?

      显然,对于一个qq号码,如果它在第一个文件中没有出现过,但是它映射的3个位置已经全部是1的情况会有吗?答案是会的,但是这种概率是可控的,可控的意思是:这种误差跟hash函数的个数和质量是有关系的,可以通过控制hash函数的个数和位数组的大小来控制误差概率至于表示3者之间的关系精确的数学公式就不再详细研究了

可以这样讲,布隆过滤器是Bit-Map的进一步扩展,对于大数据量判重,布隆过滤器可以在内存中进行判断,避免了对磁盘的读写,效率是很高的。以上是自己关于两者的理解,有错误望指教。


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/news/451490.shtml
繁体地址,请注明出处:http://hk.pswp.cn/news/451490.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

例题练习

1,购物车 功能要求:要求用户输入自己拥有总资产,例如:2000显示商品列表,让用户根据序号选择商品,加入购物车购买,如果商品总额大于总资产,提示账户余额不足,否则,购买成功…

A端,B端,C端

A端是开发界面。即管理员所接触的界面。 B端是商家界面。即浏览器界面,依托于web界面。 C端是用户界面。即app的界面,用户所接触最为广泛的界面。

怎么用js动态 设置select中的某个值为选中项

可以使用javascript和jQuery两种实现方式 1&#xff1a;使用javascript实现 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns"http://www.w3.org…

java常用简略语含义

首先这些对象都应用都是一些单词的简称&#xff0c;也是一种应用思想&#xff0c;故其他语言也可以使用&#xff0c;在 Java 里比较常见这些对象吧。下面来一一解释。 一、POJO&#xff08;Plain Ordinary Java Object&#xff09;。 简单而言&#xff0c;就是一个简单的对象&…

并行计算的强大

最近在处理一批数据&#xff0c;10的8次方&#xff0c;处理完毕大概要一个月&#xff0c;并且这个程序占用的CPU只有一个&#xff08;我从来没有注意到这个问题啊啊啊&#xff09;。 突然师兄提醒我可以把10的8次方条数据拆成10个10的7次方&#xff0c;作为10条任务并行处理&a…

Kubernetes集群(概念篇)

Kubernetes介绍 2013年docker诞生&#xff0c;自此一发不可收拾&#xff0c;它的发展如火如荼&#xff0c;作为一个运维如果不会docker&#xff0c;那真的是落伍了。 而2014年出现的kubernetes&#xff08;又叫k8s&#xff09;更加炙手可热&#xff0c;我想大部分人仅仅是听说过…

cannot resolve symbol xxxx问题

1.File->Invalidate Caches/Restart 清除缓存重启 2.还不行就maven -> Reinport

$(“#addLowForm“).serialize()同时提交其它参数的写法

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到教程。 1. 原本写法&#xff1a; 2. 不光传表单参数&#xff0c;还有别的参数的写法&#xff1a;

JAVA自学笔记25

JAVA自学笔记25 1、GUI 1&#xff09;图形用户接口&#xff0c;以图形的方式&#xff0c;来显示计算机操作的界面&#xff0c;更方便更直观 2&#xff09;CLI 命令行用户接口&#xff0c;就是常见的Dos&#xff0c;操作不直观 3&#xff09; 类Dimension 类内封装单个对象…

360——新式的流氓

360确实是一种新式的流氓。提供一些很多用户有用的工具&#xff0c;然后在同时&#xff0c;也提供一些流氓性的工具或者流浪性的推广方法&#xff0c;比如&#xff1a;对360浏览器&#xff0c;360桌面等工具&#xff0c;通过暗示性的广告语进行推广&#xff0c;而对于安装的诸多…

跳板机

现在一定规模互联网企业&#xff0c;往往都拥有大量服务器&#xff0c;如何安全并高效的管理这些服务器是每个系统运维或安全运维人员必要工作。现在比较常见的方案是搭建堡垒机环境作为线上服务器的入口&#xff0c;所有服务器只能通过堡垒机进行登陆访问&#xff0c;合格的堡…

Map是不是集合?

Map是不是集合&#xff1f; 一、起因 今天在一个群里跟几位朋友就“map是不是集合“”争执了起来&#xff1b;几位朋友一致认为map不是集合&#xff0c;他们说只有Collection接口下的才是集合&#xff0c;而我认为Collection和Map下的实现类都是集合类。二、发展 于是我开始在…

JAVA自学笔记08

JAVA自学笔记08 1、构造方法私有&#xff0c;外界就不能再创建对象 2、说明书的制作过程 1&#xff09;写一个工具类&#xff0c;在同一文件夹下&#xff0c;测试类需要用到工具类&#xff0c;系统将自动编译工具类&#xff1b;工具类的成员方法一般是静态的&#xff0c;因此…

创业,不能兼职

一直在寻找靠谱的技术人才加入自己的创业团队。这个靠谱&#xff0c;不仅是技术靠谱&#xff0c;还要有相同的价值观。价值观的概念也很广泛&#xff0c;除了人品&#xff0c;还有对一些涉及到做人做事最本质的一些理念要相同。最起码的一条是&#xff0c;你是不是真的想好了决…

Java 集合系列07之 Stack详细介绍(源码解析)和使用示例

转载 http://www.cnblogs.com/skywang12345/p/3308852.html转载于:https://www.cnblogs.com/lizhouwei/p/9162251.html

@Controller和@RestController的区别

RestController注解相当于ResponseBody &#xff0b; Controller合在一起的作用。 1)如果只是使用RestController注解Controller&#xff0c;则Controller中的方法无法返回jsp页面&#xff0c;配置的视图解析器InternalResourceViewResolver不起作用&#xff0c;返回的内容就是…

spring AOP解说

1.aop切面编程就是在常规的执行java类中方法前或执行后加入自定义的方法。 比如你本来每天都去打酱油&#xff0c;去&#xff0c;打酱油&#xff0c;回。 现在我每天在你打酱油路上等着&#xff0c;你去打酱油的时候我打你一顿&#xff0c;回来的时候给你点糖果吃。 你根本不…

接口 EnvironmentAware

凡是被Spring管理的类&#xff0c;实现接口 EnvironmentAware 重写方法 setEnvironment 可以在工程启动时&#xff0c;获取到系统环境变量和application配置文件中的变量。

简单安装ELK分析日志及使用心得

ELK是由Elasticsearch、Logstash、Kibana三个组件组成的。Elasticsearch&#xff1a;是ELK的核心插件&#xff0c;是一个基于Lucene的搜索服务器&#xff0c;它提供一个分布式多用户能力的全文搜索引擎&#xff0c;能够达到实时搜索&#xff0c;稳定&#xff0c;可靠&#xff0…

寄生式创业更容易成功

上次参加站长大会见识了不少创业团队和个人站长&#xff0c;他们中许多人都曾有过或正在过着苦逼的日子&#xff0c;不过我见到更多的还是他们风光的一面&#xff0c;在这次大会我见到了很多成功的创业团队&#xff0c;例如专门做微博营销的团队、依附于QQ空间的团队、专做腾讯…