PHP中使用BigMap實例

2020-03-24 18:57:36

字體：大中小

來源：轉載

供稿：網友

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

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。

上一篇：小貝_php源碼安裝

下一篇：有關PHPstorm的git環境的配置和git密鑰的生成總結