Hyperloglog

這也是在工作接觸到的東西，是用來做基數統計的一個方法
第一次看到真的覺得這是什麼巫術0.0

目的是要做一個按讚的系統
就是玩家可以重複對某個影片按讚，每次都要有 log，但統計按讚數時同一個玩家只計算一次

基數統計

基數 -> unique value count
第一個想到的應該就是用 hashmap，簡單好用幾乎每個程式語言都有內建
缺點就是基數大的時候空間消耗大

再來就是用 bitmap，把每個 key 都對應到某一個 bit，相較 hashmap 空間會少用一些，但長度基本上也是會越來越長

Hyperloglog 是一種基數的估算方法，上面兩種都是精確地知道不重複的數量有多少，也可以知道某個值是否出現過
而這種估計方法會有誤差，而且也無法知道某個值是否已經出現
但是相對它的速度很快，而且使用空間非常的小

Hyperloglog 基本概念

是一種機率的概念
把資料轉換成一串 bit
因為每個 bit 是 0 或是 1 的機率都是 1/2
所以從這串 bit 左邊開始看，連續有 n (n>0) 個 0 的機率是 (1/2)^n

所以當我們有很多筆資料時
需要做的就是把每筆資料都轉換成一串 bit
找出從左邊數來第一個 1 的位置 (連續0的數量+1)
例如以下三筆
00110110 -> 3
01010111 -> 2
00010010 -> 4
從中取最大值 4， 2^4 = 16 個元素
推測概念是，我們大約有了 16 筆資料，才能得到一串有連續三個 0 的資料

大致概念是上面那樣，當然直接使用會有不少誤差
所以接下來就是一堆誤差處理方法
舉個簡單的例子，像是下面這種有五筆資料，將前兩個 bit 當作 bucket number，將每個 bucket 各自取最大，再把桶子之間平均
[00] 110110 -> 1 (這筆資料在桶子[00]中不是max，被忽略)
[00] 010010 -> 2
[01] 010111 -> 2
[10] 100010 -> 1
[11] 010010 -> 2
(2+2+1+2) / 4 = 1.75
估計值 = 4 * 2^(1.75) = 13.45

因為每次資料進來都是轉換成 bit，然後看看有沒有比目前最多連續 0 的數量還多，有的話就更新一下，所以基本上只要一串 bit 的空間就可以計算基數了

Loglog 與 HyperLoglog 大概都是用這種概念去估計基數(Hyperloglog比較新)
但又會用一些方法去修正算式減少誤差(乘上常數什麼，偏差修正之類的，數學家很厲害)

詳細可以參考下面這些連結，不過每次看了都忘記，只記得概念而已
http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-iii.html
https://en.wikipedia.org/wiki/HyperLogLog
https://blog.csdn.net/u011564172/article/details/86597575

然後 Redis 內其實就有內建的 Hyperloglog 可以用了
方法很簡單

PFADD key value    // 把 value 加入基數計算內 
PFCOUNT key        // 估算出來的基數

不過工作上最後決定還是不用這個方法，因為根據流量來看按讚的人數根本就不會讓空間消耗很大QQ，而且按讚的名單也想存在 db 裡面，用了還要先經過 redis 感覺有點多此一舉(mongodb 沒有 hyperloglog)，直接簡單用 hash map 做就好了