一個關(guān)于用戶標簽的需求
為了幫助公司精準定位用戶群體，咱們需要開發(fā)一個用戶畫像系統(tǒng)，實現(xiàn)用戶信息的標簽化。
用戶標簽包括用戶的社會屬性、生活習(xí)慣、消費行為等信息，例如下面這個樣子。
通過用戶標簽，我們可以對多樣的用戶群體進行統(tǒng)計。例如統(tǒng)計用戶的男女比例、統(tǒng)計喜歡旅游的用戶數(shù)量等。
為了滿足用戶標簽的統(tǒng)計需求，小灰利用關(guān)系數(shù)據(jù)庫設(shè)計了如下的表結(jié)構(gòu)，每一個維度的標簽對應(yīng)著數(shù)據(jù)庫表中的一列：
要想統(tǒng)計所有“90后”的程序員，該怎么做呢？
用一條求交集的SQL語句即可。
看起來很簡單嘛，嘿嘿……
事情沒那么簡單，現(xiàn)在標簽越來越多，例如，用戶去過的城市、消費水平、愛吃的東西、喜歡的音樂……都快有上千個標簽了，這要給數(shù)據(jù)庫表增加多少列啊！
篩選的標簽條件過多的時候，拼出來的SQL語句像面條一樣長……
不僅如此，當對多個用戶群體求并集時，需要用distinct來去掉重復(fù)數(shù)據(jù)，性能實在太差了……
用BITMAP算法解決問題
你聽說過Bitmap算法嗎？在中文里叫作位圖算法。
這里所說的位圖并不是像素圖片的位圖，而是內(nèi)存中連續(xù)的二進制位（bit）所組成的數(shù)據(jù)結(jié)構(gòu)，該算法主要用于對大量整數(shù)做去重和查詢操作。
舉一個例子，假設(shè)給出一塊長度為10bit的內(nèi)存空間，也就是Bitmap，想要依次插入整數(shù)4、2、1、3，需要怎么做呢？
很簡單，具體做法如下。
第1步，給出一塊長度為10的Bitmap，其中的每一個bit位分別對應(yīng)著從0到9的整型數(shù)。此時，Bitmap的所有位都是0（用紫色表示）。
第2步，把整型數(shù)4存入Bitmap，對應(yīng)存儲的位置就是下標為4的位置，將此bit設(shè)置為1（用黃色表示）。
第3步，把整型數(shù)2存入Bitmap，對應(yīng)存儲的位置就是下標為2的位置，將此bit設(shè)置為1。
第4步，把整型數(shù)1存入Bitmap，對應(yīng)存儲的位置就是下標為1的位置，將此bit設(shè)置為1。
第5步，把整型數(shù)3存入Bitmap，對應(yīng)存儲的位置就是下標為3的位置，將此bit設(shè)置為1。
如果問此時Bitmap里存儲了哪些元素，顯然是4、3、2、1，一目了然。
Bitmap不僅方便查詢，還可以去掉重復(fù)的整數(shù)。
你仔細想一想，你所做的用戶標簽?zāi)懿荒苡肂itmap的形式進行存儲呢？
我的每一條用戶數(shù)據(jù)都對應(yīng)著成百上千個標簽，怎么也無法轉(zhuǎn)換成Bitmap的形式啊？
別急，我們不妨轉(zhuǎn)換一下思路，為什么一定要讓一個用戶對應(yīng)多個標簽，而不是一個標簽對應(yīng)多個用戶呢？
信息不一定非要以用戶為中心存儲，也能夠以標簽為中心來存儲，讓每一個標簽存儲包含此標簽的所有用戶ID，就像倒排索引一樣！
第1步，建立用戶名和用戶ID的映射。
第2步，讓每一個標簽存儲包含此標簽的所有用戶ID，每一個標簽都是一個獨立的Bitmap。
這樣一來，每一個用戶特征都變得一目了然。
例如，程序員和“00后”這兩個群體，各自的Bitmap分別如下所示。
BitMap好處
1.高性能的位運算
2.相比使用哈希表的話，每一個用戶ID都要用整型數(shù)據(jù)存儲，少則占用4字節(jié)（32bit），多則占用8字節(jié)（64bit）。而一個用戶ID在Bitmap中只占1bit，內(nèi)存是使用哈希表所占用內(nèi)存的1/32，甚至更少！
3.Bitmap在對用戶群做交集和并集運算時也有極大的便利
如何取反操作呢
我們可以使用異或 運算進行操作，即相同位為0，不同位為1。
同樣是剛才的例子，我們給出“90后”用戶的Bitmap，再給出一個全量用戶的Bitmap。最終要求出的是存在于全量用戶，但又不存在于“90后”用戶的部分。
實現(xiàn)方式
長度計算公式
int nSize = (width * bitPixel + 64) / 64 ;
（高效寫法是(((width * bitPixel + 64)>>6)) )
通過位移操作，可以很方便的擴容
而且越往上就是指數(shù)擴容，滿足過億級別數(shù)據(jù)量的時間復(fù)雜度也是O(1)
class MyBitmap:
def __init__(self,size):
self.words=[0]*(self.get_word_index(size-1)+1)
self.size=size
def get_bit(self,bit_index):
if bit_index<0 or bit_index>self.size-1:
raise Exception("超過Bitmap有效范圍！")
word_index=self.get_word_index(bit_index)
return (self.words[word_index]&(1<<bit_index))!=0
def set_bit(self,bit_index):
if bit_index<0 or bit_index>self.size-1:
raise Exception("超過Bitmap有效范圍！")
word_index=self.get_word_index(bit_index)
self.words[word_index] |=(1<<bit_index)
def get_word_index(self,bit_index):
#右移6位，相當于除以64
return bit_index>>6
bitMap=MyBitmap(128)
bitMap.set_bit(126)
bitMap.set_bit(75)
print(bitMap.get_bit(126))
print(bitMap.get_bit(78))
