Using BigMap instances in PHP_PHP tutorial-PHP Tutorial-php.cn

Using BigMap instances in PHP_PHP tutorial

WBOY

Release： 2016-07-13 09:58:56

Original

920 people have browsed it

Using BigMap instances in PHP

This article mainly introduces the use of BigMap instances in PHP. This article directly gives the implementation code. The code contains detailed comments. Friends in need can refer to it. Next

//The so-called Bit-map uses a bit to mark the Value corresponding to an element, and the Key is the element. Since data is stored in Bit units, storage space can be greatly saved.

If N =1; apply for memory space as int a[2];

Assuming that the total number of things that need to be sorted or searched is N=10000000, then the size of the memory space we need to apply for is int a[1 N/32], where: a[0] occupies 32 in the memory, which can correspond to the decimal number 0- 31, and so on:

1. Find the subscript corresponding to decimal 0-N in array a: n/32

2. Find the number from 0-N corresponding to 0-31: N2=M

3. Use shift 0-31 to make the corresponding 32bit bit 1: 1<

Example:

If you want to store 3

(1) a subscript 30/ 32 = 0; placed in a[0];

(2) 3% 32 = 30;

(3) Shift left 30 bits 01000000 00000000 00000000 00000000 The corresponding value $a[0] = 1073741824;

1. Find the subscript corresponding to decimal 0-N in array a:

Decimal 0-31, corresponding to a[0], first convert the decimal number n to the remainder of 32, which can be converted into the subscript corresponding to the array a. For example, n=24, then n/32=0, then the subscript corresponding to 24 in array a is 0. For example, if n=60, then n/32=1, then the subscript of 60 in array a is 1. In the same way, the subscript of 0-N in array a can be calculated.

2. Find the number from 0-N corresponding to 0-31:

Decimal 0-31 corresponds to 0-31, and 32-63 also corresponds to 0-31. That is, given a number n, the number corresponding to 0-31 can be found by modulo 32.

3. Use shift 0-31 to make the corresponding 32bit bit equal to 1.

Find the number corresponding to 0-31 as M, shift it left by M bits: that is, 2^M. Then set it to 1.

From this we calculate the space occupied by 10,000,000 bits:

1byte = 8bit

1kb = 1024byte

1mb = 1024kb

The space occupied is: 10000000/8/1024/1024mb.

Probably a little more than 1mb.

class bigMap {

//Use two bytes to save

private $mask = 0x1f ;

private $bitsperword = 32 ;

//The number of bits to shift is 5 pow(2,5) = 32

private $shift = 5 ;

//Array to store data

public $bitArray = array();

/**

The number corresponding to $i is reset to zero

function clearbit($i){

////Then the specified bit in the current byte is set to 0, and the other bits in the other party's array will remain unchanged after &. This is the wonderful use of 1

// $i>>SHIFT here is equivalent to intval($i /32);

// $i & $this->mask This is equivalent to $i % $this->mask, take the remainder

@$this->bitArray[$i >> $this->shift] &= ~(1<<($i & $this->mask));

}

/**

The number corresponding to $i is 1

function setbit($i){

@$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask));

}

//test tests whether the bit is 1

function testbit($i){

return $this->bitArray[$i >> $this->shift] & (1<<($i & $this->mask));