摘要:在中這些命令本身都是對字符串的操作。到最后一只都是一個思想,就是合,合,合,合如果要計算位,繼續(xù)合就可以了。
setbit,getbit這些命令在redis是如何儲存和獲取的呢?直接通過get獲取到的值我們?nèi)绾闻袛鄬奈皇?或者1?
本編文章可以看為[Redis中BitMap的妙用]的續(xù)篇。
在Redis中setbit,set,getbit,get這些命令本身都是對字符串(SDS)的操作。
當我們執(zhí)行setbit key (0,2,5,9,12,16,21) 1命令后,bitmap表示如下圖:
byte | bit0 | bit1 | bit2 | bit3 | bit4 | bit5 | bit6 | bit7 |
---|---|---|---|---|---|---|---|---|
byte0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
byte1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
byte2 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
執(zhí)行getbit 16,對應的byte為floor(16 / 8),bit為16%8,我們可以立刻得到對應的值為1,因為getbit為常數(shù)級計算,所以算法復雜度為O(1)
上篇文章中提到bitcount命令的參數(shù)start,end指的是byte而不是bit,所以我們?nèi)绻霚蚀_計算某bit位到bit位中1的數(shù)量,需要通過get命令將整個值取出來自己計算,下面我用PHP演示如何計算正確的結果(其實這種密集運算不適合PHP搞,但思路相同)
計算方法一:一個位一個位算(腦子不如高斯,我們一個一個加!)connect("127.0.0.1"); $cacheKey = "bitmap"; //我們將7,8,10對應的位置設置為1 $redis->setBit($cacheKey, 7, 1); $redis->setBit($cacheKey, 8, 1); $redis->setBit($cacheKey, 10, 1); $value = $redis->get($cacheKey); /** * 解包(redis返回來的是二進制字符串,我們需要把它解成對應的數(shù)字) * 關于unpack的用法,如果不了解,大家可以網(wǎng)上搜索學習,改天可以多帶帶寫篇文章分享 */ $bitmap = unpack("C*", $value); $count = 0; foreach($bitmap as $key => $number) { for($i = 0; $i < 8; $i++) { if(($number >> $i & 1) == 1) { $count++; } } }
看完之后有的同學會有疑問,代碼中($number >> $i & 1) == 1是怎么回事兒?
先不管>>,當一個數(shù)與1做與運算會發(fā)生什么?1的二進制表示為00000001,所以當與1做與運算后,如果結果為1(00000001),說明這個數(shù)的最后一位肯定為1,反之為0,而>>右移位可以幫我們將計算好的最后一位扔掉。網(wǎng)上看到一種更簡潔的寫法:
$count = 0; foreach($bitmap as $key => $number) { //主要看這一段哈,更簡潔,更有通用性 while($number) { $count += $number & 1; $n >>= 1; } }
然而天外有天,人外有人,又發(fā)現(xiàn)一個更厲害的,上面的算法循環(huán)次數(shù)等于總位數(shù),而下面這個做到了只循環(huán)包含1的位數(shù)的循環(huán)次數(shù)
$count = 0; foreach($bitmap as $key => $number) { //原理是什么?且聽我下面慢慢道來 while($number) { $number &= ($number - 1); $count++; } }
上面關鍵代碼只有一句$number &= ($number - 1);,上一個算法是一位一位的移除,這個算法是每次清除最右邊的1,因為二進制相加逢二進一,二進制數(shù)每加一,尾數(shù)就會從0變成1或者從1變成0,而每減一最后一位的1一定會變成0,這樣當我們計算$number & ($number-1)的時候,會將最右的1移除掉,比如9&8=1001&1000=1000,再比如8&7=1000&0111=0000。
上面的方法有一個最大的不確定因素就是其中1的個數(shù),如果所有的位都為1,那么我們一次循環(huán)都節(jié)省不了(1MB的數(shù)據(jù)需要循環(huán)計算1_1024_1024*8=8388608,800多W次啊,你說CPU累不累?)
計算方法二:查表法查表法是一種典型的空間換時間的算法,使用方法如下:
我們事前將一個字節(jié)(8位)對應的1的個數(shù)計算出來,放到一個數(shù)組中
//對效率要求這么高,我們請出PHP的SplFixedArray $map = SplFixedArray::fromArray( array( 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, ) ); echo "125對應的位數(shù)為:{$map[125]}" . PHP_EOL; echo "67對應的位數(shù)為:{$map[67]}" . PHP_EOL;
我在本地測試,通過查表法處理8MB的數(shù)據(jù)只需要0.7秒,而上面的方法需要2.3秒。當然上面的是8bit的表,如果改成16bit的表,速度會更快(但是空間占用會變大,根據(jù)實際情況調(diào)整)
計算方法三:variable-precision SWAR(不知道如何翻譯)這是一個不會帶來內(nèi)存壓力并且效率還可以的算法
//這個最大支持32位運算 function getCount($n) { $n = ($n & 0x55555555) + (($n >> 1) & 0x55555555); //line1 $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333); //line2 $n = ($n & 0x0f0f0f0f) + (($n >> 4) & 0x0f0f0f0f); //line3 $n = ($n & 0x00ff00ff) + (($n >> 8) & 0x00ff00ff); //line4 $n = ($n & 0x0000ffff) + (($n >> 16) & 0x0000ffff); //line5 return $n; }
一眼看上去,這什么什么啊。。(0x開頭代表十六進制0b開頭代表二進制)
0x55555555=0b0101010101010101
0x33333333=0b0011001100110011
0x0f0f0f0f=0b0000111100000011
我們將$n設置為一個比較小的數(shù),方便理解,假設$n=153(0b10011001)
第一行:
($n&0x55555555的目的是以二個位為一個分組,取出后一位)
0b10011001 & 0b01010101 = 0b00010001(獲取奇數(shù)位)
0b01001100 & 0b01010101 = 0b01000100(因為向右移動了一位,so獲取偶數(shù)位)
0b00010001 + 0b01000100 = 0b01010101(結果中沒兩位表示其中1的個數(shù))
第二行、第三行。。。到最后一只都是一個思想,就是2合1,4合1,8合1,16合1,如果要計算64位,繼續(xù)32合1就可以了。
上面的PHP都是一個字節(jié)一個字節(jié)計算的,我們知道32位的數(shù),占用4個字節(jié),在PHP如何處理比較好呢
$redis = new Redis(); $redis->connect("127.0.0.1"); $cacheKey = "bitmap" $redis->setBit($cacheKey, 1, 1); $redis->setBit($cacheKey, 12345, 1); $redis->setBit($cacheKey, 123456789, 1); //大約14MB的數(shù)據(jù)量 $value = $redis->get($cacheKey); //解壓,這里的N很重要(unsigned long (always 32 bit, big endian byte order)),因為redis里面的數(shù)據(jù)就是按大頭存的 $bitmap = unpack("N*", $value); $total = 0; foreach($bitmap as $n) { $n = ($n & 0x55555555) + (($n >> 1) & 0x55555555); $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333); $n = ($n & 0x0f0f0f0f) + (($n >> 4) & 0x0f0f0f0f); $n = ($n & 0x00ff00ff) + (($n >> 8) & 0x00ff00ff); $total += ($n & 0x0000ffff) + (($n >> 16) & 0x0000ffff); } echo $total;
本機測試:
get數(shù)據(jù)花費0.01s
unpack花費0.9s
foreach+計算花費1.48s
總花費2.46s
因為數(shù)據(jù)較大,我對2秒多的計算時間略滿意,Redis本身的bitcount會根據(jù)字符串長度自動選擇variable-precision SWAR還是查表法。
技術手段沒有什么最好,只有最合適。如果本文幫到了你,關注公眾號支持一下。
文章版權歸作者所有,未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/30542.html
摘要:如何實現(xiàn)持久化持久化,將在內(nèi)存中的的狀態(tài)保存到硬盤中,相當于備份數(shù)據(jù)庫狀態(tài)。相當于備份數(shù)據(jù)庫接收到的命令,所有被寫入的命令都是以的協(xié)議格式來保存的。 最近社區(qū)里面有一篇文章引起了最多程序猿的關注,Laravel、PHPer 面試可能會遇到的問題,看評論區(qū)不少小伙伴們被難倒,對于一些問題同樣難倒了我(其實有很多啦),趁著周末有空,又總結梳理了一遍,順便來答一波題。由于個人技術水平有限,答...
閱讀 1033·2021-11-25 09:43
閱讀 1413·2021-11-18 10:02
閱讀 1814·2021-11-02 14:41
閱讀 2366·2019-08-30 15:55
閱讀 1068·2019-08-29 16:18
閱讀 2552·2019-08-29 14:15
閱讀 1390·2019-08-26 18:13
閱讀 733·2019-08-26 10:27