0
雷鋒網(wǎng) AI 科技評論按,本文本文來自公眾號“程序員小灰”(ID:chengxuyuanxiaohui),原載于知乎,雷鋒網(wǎng)獲授權(quán)轉(zhuǎn)載。
兩個月之前——
為滿足用戶標(biāo)簽的統(tǒng)計(jì)需求,小灰利用 Mysql 設(shè)計(jì)了如下的表結(jié)構(gòu),每一個維度的標(biāo)簽都對應(yīng)著 Mysql 表的一列:
要想統(tǒng)計(jì)所有90后的程序員該怎么做呢?
用一條求交集的SQL語句即可:
Select count(distinct Name) as 用戶數(shù) from table whare age = '90后' and Occupation = '程序員' ;
要想統(tǒng)計(jì)所有使用蘋果手機(jī)或者00后的用戶總合該怎么做?
用一條求并集的SQL語句即可:
Select count(distinct Name) as 用戶數(shù) from table whare Phone = '蘋果' or age = '00后' ;
兩個月之后——
———————————————
1. 給定長度是 10 的 bitmap,每一個 bit 位分別對應(yīng)著從 0 到 9 的 10 個整型數(shù)。此時 bitmap 的所有位都是 0。
2. 把整型數(shù) 4 存入 bitmap,對應(yīng)存儲的位置就是下標(biāo)為4的位置,將此 bit 置為 1。
3. 把整型數(shù)2存入bitmap,對應(yīng)存儲的位置就是下標(biāo)為2的位置,將此bit置為1。
4. 把整型數(shù)1存入bitmap,對應(yīng)存儲的位置就是下標(biāo)為1的位置,將此bit置為1。
5. 把整型數(shù)3存入bitmap,對應(yīng)存儲的位置就是下標(biāo)為3的位置,將此bit置為1。
要問此時 bitmap 里存儲了哪些元素?顯然是 4,3,2,1,一目了然。
Bitmap 不僅方便查詢,還可以去除掉重復(fù)的整型數(shù)。
建立用戶名和用戶 ID 的映射:
讓每一個標(biāo)簽存儲包含此標(biāo)簽的所有用戶 ID,每一個標(biāo)簽都是一個獨(dú)立的 Bitmap。
3. 這樣,實(shí)現(xiàn)用戶的去重和查詢統(tǒng)計(jì),就變得一目了然:
如何查找使用蘋果手機(jī)的程序員用戶?
如何查找所有男性或者00后的用戶?
一周之后......
我們以上一期的用戶數(shù)據(jù)為例,用戶基本信息如下。按照年齡標(biāo)簽,可以劃分成 90 后、00 后兩個 Bitmap:
用更加形象的表示,90 后用戶的 Bitmap 如下:
這時候可以直接求得非90后的用戶嗎?直接進(jìn)行非運(yùn)算?
顯然,非 90 后用戶實(shí)際上只有 1 個,而不是圖中得到的 8 個結(jié)果,所以不能直接進(jìn)行非運(yùn)算。
同樣是剛才的例子,我們給定 90 后用戶的 Bitmap,再給定一個全量用戶的 Bitmap。最終要求出的是存在于全量用戶,但又不存在于 90 后用戶的部分。
如何求出呢?我們可以使用異或操作,即相同位為 0,不同位為 1。
【 圖片來源:null 所有者:null 】
25769803776 L = 11000000000000000000000000000000000 B
8589947086 L = 1000000000000000000011000011001110 B
1.解析 Word 0,得知當(dāng)前 RLW 橫跨的空 Word 數(shù)量為 0,后面有連續(xù) 3 個普通 Word。
2.計(jì)算出當(dāng)前 RLW 后方連續(xù)普通 Word 的最大 ID 是 64 X (0 + 3) -1 = 191。
3. 由于 191 < 400003,所以新 ID 必然在下一個 RLW(Word4)之后。
4.解析 Word 4,得知當(dāng)前 RLW 橫跨的空 Word 數(shù)量為 6247,后面有連續(xù) 1 個普通 Word。
5.計(jì)算出當(dāng)前 RLW(Word4)后方連續(xù)普通 Word 的最大 ID 是 191 + (6247 + 1)X64 = 400063。
6.由于 400003 < 400063,因此新 ID 400003 的正確位置就在當(dāng)前 RLW(Word4)的后方普通 Word,也就是 Word 5 當(dāng)中。
最終插入結(jié)果如下:
官方說明如下:
* Though you can set the bits in any order (e.g., set(100), set(10), set(1),
* you will typically get better performance if you set the bits in increasing order (e.g., set(1), set(10), set(100)).
*
* Setting a bit that is larger than any of the current set bit
* is a constant time operation. Setting a bit that is smaller than an
* already set bit can require time proportional to the compressed
* size of the bitmap, as the bitmap may need to be rewritten.
幾點(diǎn)說明:
該項(xiàng)目最初的技術(shù)選型并非Mysql,而是內(nèi)存數(shù)據(jù)庫hana。本文為了便于理解,把最初的存儲方案寫成了Mysq數(shù)據(jù)庫。
文中介紹的Bitmap優(yōu)化方法在一定程度上做了簡化,源碼中的邏輯要復(fù)雜得多。比如對于插入數(shù)據(jù)400003的定位,和實(shí)際步驟是有出入的。
如果同學(xué)們有興趣,可以親自去閱讀源碼,甚至是嘗試實(shí)現(xiàn)自己的Bitmap算法。雖然要花不少時間,但這確實(shí)是一種很好的學(xué)習(xí)方法。
EWAHCompressedBitmap對應(yīng)的maven依賴如下:
<dependency>
<groupId>com.googlecode.javaewah</groupId>
<artifactId>JavaEWAH</artifactId>
<version>1.1.0</version>
</dependency>
雷峰網(wǎng)版權(quán)文章,未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。