PHP中使用BigMap實(shí)例

2020-03-24 18:57:36

字體：大中小

供稿：網(wǎng)友

//所謂的Bit-map就是用一個(gè)bit位來標(biāo)記某個(gè)元素對應(yīng)的Value，而Key即是該元素。由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。若 N =1 ; 申請內(nèi)存空間為 int a[2] ; 假設(shè)需要排序或者查找的總數(shù)N=10000000，那么我們需要申請內(nèi)存空間的大小為int a[1 + N/32]，其中：a[0]在內(nèi)存中占32為可以對應(yīng)十進(jìn)制數(shù)0-31，依次類推： 1.求十進(jìn)制0-N對應(yīng)在數(shù)組a中的下標(biāo)： n/32 2.求0-N對應(yīng)0-31中的數(shù)： N%32=M3.利用移位0-31使得對應(yīng)32bit位為1: 1 M，并置1;舉例 : 如果想存儲(chǔ) 3 (1) a下標(biāo) 30/ 32 = 0 ; 放在a[0] 中; (2) 3% 32 = 30; (3) 左移 30 位 01000000 00000000 00000000 00000000 這個(gè)對應(yīng)的值$a[0] = 1073741824 ;
1.求十進(jìn)制0-N對應(yīng)在數(shù)組a中的下標(biāo)：十進(jìn)制0-31，對應(yīng)在a[0]中，先由十進(jìn)制數(shù)n轉(zhuǎn)換為與32的余可轉(zhuǎn)化為對應(yīng)在數(shù)組a中的下標(biāo)。比如n=24,那么 n/32=0，則24對應(yīng)在數(shù)組a中的下標(biāo)為0。又比如n=60,那么n/32=1，則60對應(yīng)在數(shù)組a中的下標(biāo)為1，同理可以計(jì)算0-N在數(shù)組a中的下標(biāo)。 2.求0-N對應(yīng)0-31中的數(shù)：十進(jìn)制0-31就對應(yīng)0-31，而32-63則對應(yīng)也是0-31，即給定一個(gè)數(shù)n可以通過模32求得對應(yīng)0-31中的數(shù)。 3.利用移位0-31使得對應(yīng)32bit位為1. 找到對應(yīng)0-31的數(shù)為M, 左移M位：即2^M. 然后置1. 由此我們計(jì)算10000000個(gè)bit占用的空間：1byte = 8bit1kb = 1024byte1mb = 1024kb占用的空間為：10000000/8/1024/1024mb。大概為1mb多一些。 html' target='_blank'>class bigMap { //使用兩個(gè)字節(jié)保存 private $mask = 0x1f ; private $bitsperword = 32 ; // 移位的位數(shù)為5 pow(2,5) = 32 private $shift = 5 ; // 存儲(chǔ)數(shù)據(jù)的數(shù)組 public $bitArray = array(); $i 對應(yīng)的數(shù)歸零 function clearbit($i){ ////則將當(dāng)前byte中的指定bit位取0，&后其他對方數(shù)組bit位必然不變，這就是 1 的妙用 // $i SHIFT 這里相當(dāng)于 intval($i /32) ; // $i & $this- mask 這里相當(dāng)于 $i % $this- mask ,取余 @$this- bitArray[$i $this- shift] &= ~(1 ($i & $this- mask)); $i 對應(yīng)的數(shù)致1 function setbit($i){ @$this- bitArray[$i $this- shift] |= (1 ($i & $this- mask)); //test 測試所在的bit為是否為1 function testbit($i){ return $this- bitArray[$i $this- shift] ($i & $this- mask));PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時(shí)間聯(lián)系我們修改或刪除，多謝。

上一篇：小貝_php源碼安裝

下一篇：有關(guān)PHPstorm的git環(huán)境的配置和git密鑰的生成總結(jié)