PHP中使用BigMap实例

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

<?php

//所谓的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=M

3.利用移位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 = 8bit

1kb = 1024byte

1mb = 1024kb

占用的空间为：10000000/8/1024/1024mb。

大概为1mb多一些。

*/

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] & (1<<($i & $this->mask));

}

}

$oBig = new bigMap() ;

$oBig->setbit(30) ;

var_dump($oBig->testbit(2)) ;

var_dump($oBig->bitArray) ;