PHP中使用BigMap实例

这篇文章主要介绍了PHP中使用BigMap实例,本文直接给出实现代码,代码中包含详细注释,需要的朋友可以参考下

1. <?php 
2. //所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。 
3.  
4. /* 
5.  
6. 若 N =1 ; 申请内存空间为 int a[2] ;  
7. 假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推：  
8.  
9. 1.求十进制0-N对应在数组a中的下标： n/32  
10.  
11. 2.求0-N对应0-31中的数： N%32=M 
12.  
13. 3.利用移位0-31使得对应32bit位为1: 1<<M，并置1; 
14.  
15. 举例 :  
16.  
17. 如果想存储 3  
18. (1) a下标 30/ 32 = 0 ; 放在a[0] 中;  
19. (2) 3% 32 = 30;  
20. (3) 左移 30 位 01000000 00000000 00000000 00000000 这个对应的值$a[0] = 1073741824 ;  
21.  
22.  
23. 1.求十进制0-N对应在数组a中的下标：  
24. 十进制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中的下标。  
25.  
26. 2.求0-N对应0-31中的数：  
27.  
28. 十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。  
29.  
30. 3.利用移位0-31使得对应32bit位为1.  
31.  
32. 找到对应0-31的数为M, 左移M位：即2^M. 然后置1. 
33.  
34. 由此我们计算10000000个bit占用的空间： 
35.  
36. 1byte = 8bit 
37.  
38. 1kb = 1024byte 
39.  
40. 1mb = 1024kb 
41. 占用的空间为：10000000/8/1024/1024mb。 
42.  
43. 大概为1mb多一些。 
44.  
45. */ 
46.  
47. class bigMap { 
48. //使用两个字节保存  
49. private $mask = 0x1f ; 
50. private $bitsperword = 32 ; 
51. // 移位的位数为5 pow(2,5) = 32  
52. private $shift = 5 ; 
53. // 存储数据的数组  
54. public $bitArray = array();  
55.  
56. /** 
57. $i 对应的数归零  
58. */ 
59. function clearbit($i){ 
60. ////则将当前byte中的指定bit位取0，&后其他对方数组bit位必然不变，这就是 1 的妙用 
61. // $i>>SHIFT 这里相当于 intval($i /32) ; 
62. // $i & $this->mask 这里相当于 $i % $this->mask ,取余 
63. @$this->bitArray[$i >> $this->shift] &= ~(1<<($i & $this->mask));  
64. } 
65.  
66. /** 
67. $i 对应的数致1  
68. */ 
69. function setbit($i){ 
70. @$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask));  
71. } 
72.  
73. //test 测试所在的bit为是否为1  
74. function testbit($i){  
75. return $this->bitArray[$i >> $this->shift] & (1<<($i & $this->mask));  
76. }  
77. } 
78.  
79.  
80. $oBig = new bigMap() ;  
81.  
82. $oBig->setbit(30) ;  
83.  
84. var_dump($oBig->testbit(2)) ;  
85. var_dump($oBig->bitArray) ;  
86.  
87. echo decbin($oBig->bitArray[0]),"<br>";