1. 首頁 > 生活百科 > >

4 探究Presto SQL引擎-統計計數( 二 )

生活百科


2.2 Linear Count算法Linear Count簡稱LC算法，LC算法的流程非常簡單(背后的數學思想不簡單) 。
算法描述如下：

  • 初始化：給定m個房間，房間存儲數字，初始化為0 。
  • 迭代執行：對于要進行基數統計的集合 ， 用一個哈希函數處理集合中的每一個元素 。通過哈希函數處理后，元素就可以放置到一個房間中 。
  • 收尾：統計m個房間中空房間的數量U 。
  • 結論：集合中不重復元素的個數估計值可以通過如下公式計算：n=-m*log(U/m) 。
這樣就把一個統計問題轉換成了一個數學問題 。公式非常簡潔 ， 看到這里大腦中一定會出現許多的問題：
這個公式是怎么得到的？
這里涉及到概率論與數理統計知識，簡單來說就是分布、期望、方差、最大似然估計 。數學相關的知識比較初級，陳希孺的《概率論與數理統計》基本能覆蓋這個公式的數學原理 。
這個算法的精確度怎么樣？
這個問題從數學的角度，就是問方差(標準差) 。這里沒法給一個具體的值，跟滿桶率控制，m的選擇有關 。
這個算法相比精確計數很省空間嗎？
這個毋庸置疑，不然直接精確統計就可以了 。
m和最終結果n需要滿足什么關系？
（畢竟當沒有空房間時 ， 這個公式就有問題了 。） 這里直接給結論吧，隨著m和n的增大 ， m大約為n的十分之一 。
2.3 HyperLogLog算法HyperLogLog簡稱HLL算法 ， 它有如下的特點：
  1. 可以實現由極小的內存開銷統計出巨量的數據 。在 Redis中實現的HyperLogLog，只需要12K內存就能統計2^64個數據 。
  2. 可以方便實現分布式擴展 。(這個點對算法在業務系統中落地非常關鍵)
理解HLL算法，需要如下幾個知識點的鋪墊：伯努利實驗、調和平均數 。
伯努利實驗有很多的呈現方式，本文例舉其中的一種： 取一枚硬幣，不斷拋擲，直到硬幣落地結果為正面朝上 。這樣的執行過程稱為一輪實驗 。從描述可以看出一輪實驗完成拋擲硬幣的次數是隨機的 。
一輪實驗對應的Java代碼實現如下：
private Random random = new Random(); /*** 0代表正面* 1代表反面* 拋擲直到出現正面* @return 拋擲的次數*/ public int tossCoin(){int r,cnt=0;do{r=random.nextInt(2);cnt++;}while (r<1);return cnt; }可以看出，每執行一輪實驗就會得到一個數字，代表這輪實驗拋擲硬幣的次數 。例如：
執行了10輪，可能的結果如下：
3,1,4,1,1,2,3,4,1,1執行了100輪，可能的結果如下：
1,1,2,1,1,2,1,4,2,1,3,1,1,1,1,3,1,2,1,1,2,4,2,3,2,1,1,1,3,1,2,2,6,1,2,4,1,2,2,1,1,3,1,1,1,1,1,1,1,1,1,4,2,1,1,1,1,1,3,1,2,4,4,4,1,3,2,1,5,1,1,1,1,1,1,1,5,1,1,7,1,1,4,1,3,2,1,1,5,2,1,1,5,2,1,1,4,1,1,1執行了1000輪，可能的結果如下：
1,2,1,2,1,3,3,3,1,1,2,2,1,2,1,1,1,1,1,2,1,7,1,1,1,2,2,1,1,3,5,2,3,2,3,1,1,3,1,...,4,1,1,1,2,2,1,3,1,1,1,2,1,1,1,2,1,4,2,2,1,2,2,2,1,1,1,2,2,2,1,1,1,2,2,1,1,3,2,6,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,2,1這時候問題就來了，我們這樣按上面的規則不停的拋硬幣只是為了應付無聊的時間嗎？當然不是！我們關注的重點是：
4 探究Presto SQL引擎-統計計數

文章插圖
當然，這個最大值是隨機變動的，它不是一個固定的值 。但是隱約中有個規律：執行的輪次越多，輪次對應的最大值也越大 。數學上可以給一個很粗略的公式來擬合這種關系：n=2^p 。
換言之，我們可以通過p來估計n 。到這里就出現了問題解決思路的轉換：
將基數統計問題轉換成概率論里面參數估計的問題 。
思維轉換到了數學領域，就可以用數學的工具來解決問題 。通常用概率論的思維解決問題 ， 會面臨如下幾個攔路虎 。
問題一：最大值不穩定 ， 容易受到極值影響 。
在概率上，對于極值我們的處理策略是多實驗幾輪，通過平均值來消除極值的影響 。這個就引出了第二基礎知識點：調和平均數 。
數學上其實有許多的平均數計算方式：算術平均數、幾何平均數、平方平均數 。這里選用調和平均數主要是消除極值的影響 。通常有個笑話說，我的收入是1萬 ， 老板的收入是1億，我們平均收入是5000萬，我被平均了 。如果用調和平均數 ， 得到的結果就是1999.98 。
關于調和平均數的公式，非常容易理解：
4 探究Presto SQL引擎-統計計數

推薦閱讀