大数据计数原理1+0=1这你都不会算(九)No.64
source link: http://mp.weixin.qq.com/s/yx-GEjtRKRt3BhIHIS7e-w
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
大数据计数原理1+0=1这你都不会算(九)No.64
Original 大蕉 一名叫大蕉的程序员 2017-10-26 15:03 Posted on
大数据计数原理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+0=1这你都不会算(六)No.57 <- LinearCounting（一）
大数据计数原理1+0=1这你都不会算(七)No.59 <- LinearCounting（二）
大数据计数原理1+0=1这你都不会算(八)No.60 <- RoaringBitMaps
啦啦啦~有小伙伴说我最近怎么不更新，其实最近真的很忙，而且有很多新的东西要去学，连论文都只能抽时间看。今天这个算法说实话很难理解，但是确实是一个很好很好巨好的基数估计算法。叫做LogLogCounting，出自论文《Loglog Counting of Large Cardinalities》，人称LLC。
这么举例子吧，跟你聊聊这个算法有多节省内存。假如我们有1亿数据基数，使用HashSet可能需要2G内存，使用BitMap需要大概12.5M，使用LinearCounting需要1.25M，使用LLC只需要640字节，连1K都不需要。
我们都知道，基数统计的前提就是hash函数要足够好。什么叫足够好？分布均匀、长度一致、碰撞可忽略。怎么取？主流加密算法基本都可以。
好了牛逼吹完了，想了解到这个程度的可以左上角退出了嗷。下面是严肃的数学时间，我尽量讲得不那么数学。
首先，这个算法的第一要义是什么？靠猜。
比如我们Hash完的串为0100，1000，0010。等，我们发现这些串第一个1出现的位置在第3位上（按1、2、3、4这样从左往右数），那我们就猜，总共有2^3这么多个数。主要算法思路就是上面这样，取第一个1出现的位置，然后靠猜。
那么问题来了，我们为什么可以这样猜呢？这就需要概率论的知识了。
我们假设字符串"Banana"（简称为B），通过hash之后得到了一大堆的01的比特串，因为我们的hash算法非常好，所以每一个bit位为0和为1的概率就是五五开，都是50%这样。
那我们就把他当成是薛定谔的猫了，我完全不知道这个bit位有没有猫，只有谜底揭晓的时候才知道。我们把所有装着盒子的猫一字排排开，从头开始找。第一个盒子找不到猫（标记bit位为0）的概率为1/2，第二个盒子就找到猫的概率为1/(2^2)，第k个盒子就找到猫的概率为1/(2^k)。
好，接下来假设我们总共要找n次，也就是有n个B进行hash。
考虑第一个问题。第一个B进行Hash后，在第k个位置第一次找到猫的概率为1-1/(2^k)，那么明显，进行n次的结果后，所有的寻找次数加起来，都最多在第k个位置第一次找到猫的概率P( X <= k )= (1-1/(2^k))^n。当n远大于2^k的时候，P( X <= k )的概率几乎为0，好了我们找到了一个上限。
接下来我们考虑第二个问题。那么如果考虑每一次的结果都大于k呢？概率P( X >= k) = 1 - (1-1/(2^k))^n。由极限定理可以得到，当n远小于2^k的时候，P( X >= k )的概率几乎为0。
那么我们就得到说，无论是n远大于2^k 时，P的概率很小。无论是n远小于2^k 时，P的概率也很小。那既然这样，我们就直接拍脑袋取2^k了嘛。
所以LLC的基本思想就是。我们先拍一个大概的数据范围，也就是统计的上限，比如你的数据量是大概1亿，1百亿还是1千亿，这样拍一个，然后选hash算法均匀分配到他们身上。意思就是，如果我们的基数是1千亿，那么我们致至少要有足够多的bit位空间来保存这上限也就是一千亿。在实际进行统计的时候，我们进行n次hash之后，如果第一个找到1的位置是k，那么就可以估计这个基数是2^k。
基础算法到这里就说完了，我们也说了，我们是靠猜的，那能不能猜得靠谱些？
我猜几十次几百次取平均，应该大概或许能降低这个误差吧？这就有了分桶的思想，我们只需要每个桶记住自己桶的位置以及桶里边最大的k值，就可以了。
我们假设分桶树为16，也就是2^4。那我们就取hash值的前四个bit来进行分桶，把每个桶的max保留起来即可。为什么可以这样保留？因为我们把它界定在某一个桶之后，那它的第一个1肯定是在桶内的，这时候我们就可以对比一下当前桶内的max值，进行合并。然后最终的时候，直接取一下所有桶值得平均即可。
主线就这样说完了，先消化一下，下一次我们继续聊聊，如何降低误差，如何把LogLogCounting 算法改进成无偏估计，改进完的算法误差率究竟在什么样的范围。棒~~掰掰
如果你相信童话
Recommend
-
111
大数据计数原理1+0=1这你都不会算(五)-51CTO.COM 大数据计数原理1+0=1这你都不会算(五) 作者：大蕉 2017-09-30 08:05:41
-
85
计数系统杂谈 王伟@招聘 技术...
-
49
-
75
-
46
本期我们迎来了编辑团队的新成员，来自复旦大学计算机的在读博士老田和电闪雷鸣。哈哈，邀请不到大牛，把大牛的学生挖过来也不错。本期他们将为我们介绍人群计数的相关技术和进展，欢迎感兴趣的朋友阅读
-
14
大数据不再只是一个流行词，而是一个强大的行业。据预测，到2021年，平均每人每秒将产生约1.7M的数据。 要知道大数据对个人和企业的日常工作效率的重要性，了解最大的趋势是很重要的。
-
7
本文作者为中国人民大学统计学院饶燕芳同学，由 COS 编辑部审核发表，略有修改。点击此处下载 / 阅读本文 PDF 版本 一、问题的引出 在数据分析和数...
-
4
【redis进阶(2)】大数据量模糊计数HyperLogLog 提供不精确的去重计数方案，用于记录大数据量的计数（如，网站的uv），虽然不精确但是也不是非常不精确，标准误差是 0.81%。HyperLog...
-
2
金三银四，又到了换工作的最佳时机，我幻想着只要跳个槽，就能离开这个”鸟地方“，拿着更多的钱，干着最爽的事... 然而现实总是残酷的，最近有个学妹在换工作，面试前什么手写Priomise、vue...
-
8
自私，你都不会？王智远·2022-06-06 01:00希望你能收获「无需抱歉」的关系。对别人好是公认的美德。 的...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK