大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(六)
照例甩一波鏈接。
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(一)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(二)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(三)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(四)
大數(shù)據(jù)計(jì)數(shù)原理1+0=1這你都不會(huì)算(五)
今天開(kāi)始進(jìn)入一個(gè)全新的領(lǐng)域，嗯，叫基數(shù)估計(jì)。
什么叫基數(shù)估計(jì)呢?
基數(shù)是指一個(gè)一大堆值集合中，不同的值的個(gè)數(shù)。
我們之前講的，都是精確的統(tǒng)計(jì)，有一說(shuō)一有二說(shuō)二，直接去重統(tǒng)計(jì)就可以了。
基數(shù)估計(jì)，故名思議，估計(jì)，意思就是使用概率論的思想，用更低空間更低時(shí)間的成本，以一個(gè)很低很低的誤差率來(lái)估計(jì)數(shù)據(jù)的基數(shù)。
能不能說(shuō)說(shuō)人話(huà)呢?
好好好，你長(zhǎng)得好看說(shuō)什么都對(duì)。
加入一個(gè)集合長(zhǎng)這樣
{大蕉，小蕉，小蕉，大大蕉，小蕉}
統(tǒng)計(jì)思想會(huì)這樣說(shuō)。
啊大蕉，嗯，1個(gè)。
小蕉，沒(méi)出現(xiàn)過(guò)，嗯，2個(gè)。
小蕉，出現(xiàn)過(guò)了，嗯，2個(gè)。
大大蕉，沒(méi)出現(xiàn)過(guò)，嗯，3個(gè)。
小蕉，出現(xiàn)過(guò)了，嗯，3個(gè)。
概率論思想會(huì)這樣說(shuō)。
我夜觀天象，掐指一算，公子是個(gè)喜脈。
呸呸呸。掐值一算，有99%的概率是3個(gè)。
但是又有小伙伴開(kāi)始說(shuō)了，我特么把手都快掐出血了，也不知道你吖是怎么估算的。
年輕人不要太著急嘛。
我們今天幾乎所有算法的啟蒙。Linear Counting(LC)
來(lái)自于1900年一個(gè)叫 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.
意思就是，啊傳統(tǒng)的精確統(tǒng)計(jì)至少要O(q log q)這么死鬼多時(shí)間，我們只需要O(q) ，你不覺(jué)得很厲害嗎?然后我們是用 Hash 實(shí)現(xiàn)的，嗯，可牛逼了。
怎么做的呢?
我們先創(chuàng)建一個(gè)長(zhǎng)度為m的數(shù)組，每一個(gè)bit都設(shè)置為0，然后搞個(gè)Hash算法把這些值的位置所對(duì)應(yīng)的0改為1。
比如字符串 “小蕉寫(xiě)得這么給力你不點(diǎn)個(gè)贊嗎”，經(jīng)過(guò) Hash 算法1、Hash 算法2、Hash 算法3，生成了數(shù)字，1、11、21。
這時(shí)候又來(lái)了一個(gè)字符串 “小蕉寫(xiě)得這么給力你不點(diǎn)個(gè)贊”，經(jīng)過(guò) Hash 算法1、Hash 算..
你等等等等等，這不是BitMap嗎?你特么在說(shuō)啥。
年輕人不要太著急嘛。
我急!這輩子就現(xiàn)在!最!急!
好好好我來(lái)了我來(lái)了。上面這個(gè)數(shù)組比BitMap所需要的數(shù)組小很多很多很多。然后我們假設(shè)最終有u個(gè)位置還是0。我們給出一個(gè)極大似然估計(jì)，估計(jì)一下n的估計(jì)(下面這個(gè)是極大似然估計(jì))就長(zhǎng)這樣。
好了我要睡覺(jué)了，拜拜。
至于詳細(xì)的數(shù)學(xué)推導(dǎo)及誤差分析推導(dǎo)，且聽(tīng)下回分...
【本文為51CTO專(zhuān)欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)作者微信公眾號(hào)“一名叫大蕉的程序員”獲取授權(quán)】
