漫畫:什麼是Bitmap演算法?
兩個月之前——
為滿足使用者標籤的統計需求,小灰利用Mysql設計瞭如下的表結構,每一個維度的標籤都對應著Mysql表的一列:
要想統計所有90後的程式設計師該怎麼做呢?
用一條求交集的SQL語句即可:
Select count(distinct Name) as 使用者數 from table whare age = '90後' and Occupation = '程式設計師' ;
要想統計所有使用蘋果手機或者00後的使用者總合該怎麼做?
用一條求並集的SQL語句即可:
Select count(distinct Name) as 使用者數 from table whare Phone = '蘋果' or age = '00後' ;
兩個月之後——
———————————————
1. 給定長度是10的bitmap,每一個bit位分別對應著從0到9的10個整型數。此時bitmap的所有位都是0。
2. 把整型數4存入bitmap,對應儲存的位置就是下標為4的位置,將此bit置為1。
3. 把整型數2存入bitmap,對應儲存的位置就是下標為2的位置,將此bit置為1。
4. 把整型數1存入bitmap,對應儲存的位置就是下標為1的位置,將此bit置為1。
5. 把整型數3存入bitmap,對應儲存的位置就是下標為3的位置,將此bit置為1。
要問此時bitmap裡儲存了哪些元素?顯然是4,3,2,1,一目瞭然。
Bitmap不僅方便查詢,還可以去除掉重複的整型數。
1. 建立使用者名稱和使用者ID的對映:
2. 讓每一個標籤儲存包含此標籤的所有使用者ID,每一個標籤都是一個獨立的Bitmap。
3. 這樣,實現使用者的去重和查詢統計,就變得一目瞭然:
1. 如何查詢使用蘋果手機的程式設計師使用者?
2. 如何查詢所有男性或者00後的使用者?
一週之後......
我們以上一期的使用者資料為例,使用者基本資訊如下。按照年齡標籤,可以劃分成90後、00後兩個Bitmap:
用更加形象的表示,90後用戶的Bitmap如下:
這時候可以直接求得 非 90後的使用者嗎?直接進行非運算?
顯然,非90後用戶實際上只有1個,而不是圖中得到的8個結果,所以不能直接進行非運算。
同樣是剛才的例子,我們給定90後用戶的Bitmap,再給定一個全量使用者的Bitmap。最終要求出的是存在於全量使用者,但又不存在於90後用戶的部分。
如何求出呢?我們可以使用 異或 操作,即相同位為0,不同位為1。
25769803776L = 11000000000000000000000000000000000B
8589947086L = 1000000000000000000011000011001110B
1.解析Word0,得知當前RLW橫跨的空Word數量為0,後面有連續3個普通Word。
2.計算出當前RLW後方連續普通Word的最大ID是 64 X (0 + 3) -1 = 191。
3. 由於 191 < 400003,所以新ID必然在下一個RLW(Word4)之後。
4.解析Word4,得知當前RLW橫跨的空Word數量為6247,後面有連續1個普通Word。
5.計算出當前RLW(Word4)後方連續普通Word的最大ID是191 + (6247 + 1)X64 = 400063。
6.由於400003 < 400063,因此新ID 400003的正確位置就在當前RLW(Word4)的後方普通Word,也就是Word5當中。
最終插入結果如下:
官方說明如下:
* 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. 複製程式碼
幾點說明:
1. 該專案最初的技術選型並非Mysql,而是記憶體資料庫hana。本文為了便於理解,把最初的儲存方案寫成了Mysq資料庫。
1.文中介紹的Bitmap優化方法在一定程度上做了簡化,原始碼中的邏輯要複雜得多。比如對於插入資料400003的定位,和實際步驟是有出入的。
2.如果同學們有興趣,可以親自去閱讀原始碼,甚至是嘗試實現自己的Bitmap演算法。雖然要花不少時間,但這確實是一種很好的學習方法。
EWAHCompressedBitmap對應的maven依賴如下: 複製程式碼
<dependency> <groupId>com.googlecode.javaewah</groupId> <artifactId>JavaEWAH</artifactId> <version>1.1.0</version> </dependency>複製程式碼
—————END—————
喜歡本文的朋友們,歡迎長按下圖關注訂閱號 程式設計師小灰 ,收看更多精彩內容