大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(八)
插播一條新聞，為什么要插播，嗯不知道可能今天心情比較好，畢竟中秋了嘛~
今天跟小伙伴們聊聊另外一個統(tǒng)計算法, Roaring BitMaps。
這個改怎么翻譯呢??咆哮的位圖?s?我翻譯不出來，但是小蕉頭一歪，就給它起了一個狂拽酷霸叼扎天的翻譯 -> 咆哮吧，位圖君們。
照例甩一波鏈接。
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(一)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(二)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(三)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(四)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(五)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(六)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(七)
來了喔。
根據(jù)官方統(tǒng)計，已經(jīng)有這么多大項(xiàng)目在用Roaring BitMaps了，老牛逼了。
- Apache Lucene and derivative systems such as Solr and Elasticsearch,
- Metamarkets’ Druid,
- Apache Spark,
- Apache Hive,
- Apache Tez,
- Netflix Atlas,
- LinkedIn Pinot,
- OpenSearchServer,
- Cloud Torrent,
- Whoosh,
- Pilosa,
- Microsoft Visual Studio Team Services (VSTS),
- Jive Miru,
- eBay’s Apache Kylin.
那么勤勞又聰明的你一定會問了，這是什么東西?用來干啥的?怎么用的?從用途來看，Roaring BitMaps 就是一個用來進(jìn)行基數(shù)統(tǒng)計的算法。
用途有三只：
***只當(dāng)然就是基數(shù)統(tǒng)計啦，count之類的，可節(jié)省空間了。
第二只呢，數(shù)據(jù)庫在執(zhí)行Join的時候，要知道Join之前是多少量級，Join完又是什么量級，再執(zhí)行相應(yīng)的優(yōu)化策略。
第三只呢，是作為索引存在，可以作為數(shù)據(jù)庫判斷***索引的***性。
等等。
關(guān)于這個算法呢，也不是什么非常難的東西，原始論文其實(shí)講得蠻詳細(xì)的了，看看原始論文一般就能看懂了。但小蕉在這里，其實(shí)用三句話就可以把這個算法說清楚了。
1、把n長的區(qū)間劃分為2^16個桶(n為Roaring BitMaps 的總長度)，每個桶放一個Container，作為一級索引存在。
2、每個int數(shù)值k為32位的bit，我們?nèi)∏?6位找到對應(yīng)的桶(k % 2^16)，Container里面只保存后16位 (k mod 2^16) 。若Container為BitMap，直接把第 (k mod 2^16) 位設(shè)置為1即可，若Container為Array，則用二分查找插入法，有序插入。
3、若一個Container里面的Integer數(shù)量小于4096，就用Short類型的有序數(shù)組來存儲值。若大于4096，就用BitMap來存儲值。數(shù)據(jù)用來放稀疏的數(shù)據(jù)，BitMap用來放緊密的數(shù)據(jù)(至于為啥，請重新看BitMap的定義及使用范圍)。
實(shí)際使用的時候怎么找到值呢?跟原來插入值一樣，因?yàn)镃ontainers是有序的嘛，也有自己的數(shù)據(jù)范圍，所以首先用二分查找找到數(shù)據(jù)對應(yīng)的Container。然后分兩種情況，如果是Container是數(shù)組，就再用一次二分查找。如果Container是BitMap，直接找到對應(yīng)的位是不是1就行了。
好啦，算法方面就這樣說完了，但是又有小朋友要問了，那這樣存儲完有什么用呢?只需要定義三種操作，AND,OR,NOT，就可以快速進(jìn)行兩個集合的操作了。
因?yàn)镃ontainer有兩種，BitMap和Array ，所以進(jìn)行合并操作的時候會有三種情況。
1、Array vs Array
2、Array vs BitMap
3、BitMap vs BitMap
分別是怎么處理呢，下面所說的操作指的你所希望的功能是AND、OR、還是NOT?選一種操作進(jìn)行計算就行了。
Array vs Array ，直接用算法merge成一個數(shù)組，再進(jìn)行相應(yīng)的操作即可。
Array vs BitMap，遍歷一下Array，把它的值一個一個映射到BitMap上并操作，最終統(tǒng)計一下BitMap即可。
BitMap vs BitMap，直接按位操作即可。
實(shí)際實(shí)現(xiàn)的時候，不僅僅會有Short類型的Array，拓展開可以是任何基礎(chǔ)數(shù)據(jù)類型的Array，功能越來越豐富了。
關(guān)于論文和Github地址，后臺直接回復(fù) Roaring 可以獲取到。
沉迷學(xué)習(xí)，日漸消瘦。大家如果有什么健身、Java入門、大數(shù)據(jù)、機(jī)器學(xué)習(xí)入門方面的問題也可以問我，我看到會回的，有什么想看的想聽的也可以告訴我，我會把放入我的需求池的，啊哈哈哈哈哈。
都看到這了，真愛的你，不點(diǎn)個贊嗎?
【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】
