如果老板讓你統(tǒng)計(jì)一個(gè)實(shí)時(shí)的數(shù)據(jù)流中元素出現(xiàn)的頻率，并且準(zhǔn)備隨時(shí)回答某個(gè)元素出現(xiàn)的頻率，不需要的精確的計(jì)數(shù)，那該怎么辦？
直覺(jué)告訴我們可能需要一個(gè)巨大的 HashMap 來(lái)統(tǒng)計(jì)各個(gè)元素的出現(xiàn)頻率，但由于不同的元素的個(gè)數(shù)可能非常大，以至于是個(gè)天文數(shù)字，要求的內(nèi)存可能會(huì)非常大，從而不切實(shí)際。同時(shí)，又要求我們實(shí)時(shí)計(jì)算，實(shí)時(shí)回答，當(dāng)HashMap的沖突很高時(shí)，最壞的情況的時(shí)間復(fù)雜度可能無(wú)法滿足實(shí)時(shí)的要求。
加上前面要求不需要精確的計(jì)數(shù)，這么說(shuō)來(lái)，必須尋找新的算法。
那么，Count-Min Sketch 就是用來(lái)解決此類(lèi)問(wèn)題的算法。
這個(gè)算法的技巧是：不存儲(chǔ)所有的不同的元素，只存儲(chǔ)它們Sketch的計(jì)數(shù)。
基本的思路是這樣的：
- 創(chuàng)建一個(gè)長(zhǎng)度為 x 的數(shù)組，用來(lái)計(jì)數(shù)，初始化每個(gè)元素的計(jì)數(shù)值為 0；
- 對(duì)于一個(gè)新來(lái)的元素，哈希到 0 到 x 之間的一個(gè)數(shù)，比如哈希值為 i，作為數(shù)組的位置索引；
- 這是，數(shù)組對(duì)應(yīng)的位置索引 i 的計(jì)數(shù)值加 1；
- 那么，這時(shí)要查詢(xún)某個(gè)元素出現(xiàn)的頻率，只要簡(jiǎn)單的返回這個(gè)元素哈希望后對(duì)應(yīng)的數(shù)組的位置索引的計(jì)數(shù)值即可。
考慮到使用哈希，會(huì)有沖突，即不同的元素哈希到同一個(gè)數(shù)組的位置索引，這樣，頻率的統(tǒng)計(jì)都會(huì)偏大。
如何優(yōu)化？
使用多個(gè)數(shù)組，和多個(gè)哈希函數(shù)，來(lái)計(jì)算一個(gè)元素對(duì)應(yīng)的數(shù)組的位置索引；
那么，要查詢(xún)某個(gè)元素的頻率時(shí)，返回這個(gè)元素在不同數(shù)組中的計(jì)數(shù)值中的最小值即可。
改進(jìn)的算法比原始的算法精確多了，但還是會(huì)有沖突，但是沖突少多了。
算法評(píng)價(jià)
- 只會(huì)估算偏大，永遠(yuǎn)不會(huì)偏?。?/li>
- 只需要固定大小的內(nèi)存和計(jì)算時(shí)間，和需要統(tǒng)計(jì)的元素多少無(wú)關(guān)；
- 對(duì)于低頻的元素，估算值相對(duì)的錯(cuò)誤可能會(huì)很大。
- 這個(gè)其實(shí)就是bloom過(guò)濾器在統(tǒng)計(jì)方面的變型
