前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >大数据计数原理1+0=1这你都不会算(六)No.57

大数据计数原理1+0=1这你都不会算(六)No.57

作者头像
大蕉
发布2018-02-05 18:52:01
5470
发布2018-02-05 18:52:01
举报

照例甩一波链接。

大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet

大数据计数原理1+0=1这你都不会算(二)No.50 <- BitMap

大数据计数原理1+0=1这你都不会算(三)No.51 <- BloomFilter

大数据计数原理1+0=1这你都不会算(四)No.52 <- B-Tree

大数据计数原理1+0=1这你都不会算(五)No.55 <- B+Tree

今天开始进入一个全新的领域,嗯,叫基数估计。

什么叫基数估计呢?

基数是指一个一大堆值集合中,不同的值的个数。

我们之前讲的,都是精确的统计,有一说一有二说二,直接去重统计就可以了。

基数估计,故名思议,估计,意思就是使用概率论的思想,用更低空间更低时间的成本,以一个很低很低的误差率来估计数据的基数。

能不能说说人话呢?

好好好,你长得好看说什么都对。

加入一个集合长这样

{大蕉,小蕉,小蕉,大大蕉,小蕉}

统计思想会这样说。

啊大蕉,嗯,1个。

小蕉,没出现过,嗯,2个。

小蕉,出现过了,嗯,2个。

大大蕉,没出现过,嗯,3个。

小蕉,出现过了,嗯,3个。

概率论思想会这样说。

我夜观天象,掐指一算,公子是个喜脉。

呸呸呸。掐值一算,有99%的概率是3个。

但是又有小伙伴开始说了,我特么把手都快掐出血了,也不知道你吖是怎么估算的。

年轻人不要太着急嘛。

我们今天几乎所有算法的启蒙。Linear Counting(LC)

来自于1900年一个叫 KY · Whang 的大湿的一篇名叫《A linear-time probabilistic counting algorithm for database applications》的论文。

This algorithm has O(q) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, which has O(q log q) time complexity. Our technique, called linear counting, is based on hashing.

意思就是,啊传统的精确统计至少要O(q log q)这么死鬼多时间,我们只需要O(q) ,你不觉得很厉害吗?然后我们是用 Hash 实现的,嗯,可牛逼了。

怎么做的呢?

我们先创建一个长度为m的数组,每一个bit都设置为0,然后搞个Hash算法把这些值的位置所对应的0改为1。

比如字符串 “小蕉写得这么给力你不点个赞吗”,经过 Hash 算法1、Hash 算法2、Hash 算法3,生成了数字,1、11、21。

这时候又来了一个字符串 “小蕉写得这么给力你不点个赞”,经过 Hash 算法1、Hash 算..

你等等等等等,这不是BitMap吗?你特么在说啥。

年轻人不要太着急嘛。

我急!这辈子就现在!最!急!

好好好我来了我来了。上面这个数组比BitMap所需要的数组小很多很多很多。然后我们假设最终有u个位置还是0。我们给出一个极大似然估计,估计一下n的估计(下面这个是极大似然估计)就长这样。

好了我要睡觉了,拜拜。

至于详细的数学推导及误差分析推导,且听下回分...

这行字是提前打的

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-09-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 一名叫大蕉的程序员 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
大数据
全栈大数据产品,面向海量数据场景,帮助您 “智理无数,心中有数”!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档