工作中、面试中经常被问到上万条数据如何利用最小的空间存储,如何快速检索出数据?
经过多方面的资料收集,我们来看看 php实现位图法 是怎么做的。
1、我们知道 1G=1024M 1M=1024KB 1KB=1024byte 1byte=8bit 也就是一个字节等于8bit 也就是8个二进制位,位图法的概念是用一个位来标记某个数的存放状态,所以节省了大量的空间。
2、数据结构
unsigned int bit[N] 这个数组里面,可以储存 N * PHP_INT_SIZE *8 个数据,但最大的数是 N * PHP_INT_SIZE *8-1。 例如我们要存储的数据范围为0-63,则我们只需要将 N=1 ,这样就可以把数据存进去。
例外: 操作系统分32位 和 64位 32位 PHP_INT_SIZE =4 64位 PHP_INT_SIZE =8
如果是32位系统 ,则 N=2
如果是64位系统 ,则 N=1
数据为[5,1,7,15,0,4,6,10,14],将这些数据存入这个结构中为
下面我们来研究研究算法:
在说算法之前,先普及一下位移知识
符号 | 名称 | 说明 (转移完成后是二进制数) | 示例 | 总结 |
<< | 左移 | 把左边的数 向左移动 多少位,不够 以0补全 | 1<<0 等同于 1 等于 1 1<<1 等同于 10 等于 2 1<<2 等同于 100 等于 4 1<<3 等同于 1000 等于 8 | - |
| | 按位或 | 两个数有一个是1 就等于1 不进位加法 | 3|2 换成二进制 11 | 10 =11 等于3 | 多位二进制也是一样,遵循规则, 11 和 10 ,我们转换成十进制来说 十位上都一样,是1 ,个位是只要有一个数是 1 就是1 ,则 等到11 ,11换算成二进制就是3 |
& | 按位与 | 只有两个数都为1时 等于1 不进位加法 | 3&2 换成二进制 11 & 10 =10 等于2 | |
^ | 按位异或 | 两个数不相等则等于1 ,相等则等于0 | ||
~ | 取反 | |||
用途:
使用上面介绍的运算符可以很轻松地实现权限管理
//定义权限 $create = 1; $update = 2; $read = 4; $delete = 8; $all = $create | $update | $read | $delete; //定义用户组权限$admin = $all; //管理员拥有所有权限$guest = $create | $read; //访客只有添加和读权限$user = $all & ~$delete; //用户拥有除了删除以外的所有权限 //判断某个组是否拥有某个权限var_dump($user & $update, $user & $delete, $guest & $update);#=>int(2) int(0) int(0)
bitMap 方法 把数组位图化,并以数组的形式返回:
function bitmap($data, $int = 10) { $bitmap = array_fill(0, $int, 0); $int_bit_size = PHP_INT_SIZE * 8; foreach ($data as $item) { //字节位置 $bytePos = $item / $int_bit_size; $bitPos = $item % $int_bit_size; $position = 1 << $bitPos; isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0; // printf("item:%d position:%d 格子:%d 表达式:%d|%d=%d\n", $item, $position, $bytePos, $bitmap[$bytePos], $position, $bitmap[$bytePos] | $position); $bitmap[$bytePos] = $bitmap[$bytePos] | $position; } return $bitmap; }
调用方法:
$arr = [5, 1, 7, 15, 0, 4, 6, 10, 14, 88]; $bitmap = bitmap($arr);
===================简单对bitmap做个介绍===========================
$arr = [0, 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];
$bit_int_size=PHP_INT_SIZE*8; 这个结果是32 按理说,可以存储32个数据,
PHP_INT_MAX php最大值是 2147483647
当储存大于这个数字的时候,位移 会现出 -1 的情况
为了避免这个问题, 我们把bit_int_size=PHP_INT_SIZE*8-1 少保存一个,这样最大保存 2147483647 就不会出现负数。
这里的一个改动,其他地方也要 跟着进行修改。
===================简单对bitmap做个介绍===========================
位图化的转成原始数组:
function getdata($bitmap) { $int_bit_size = PHP_INT_SIZE * 8; $result = array(); // $num = 0; foreach ($bitmap as $key => $value) { for ($i = 0; $i < $int_bit_size; $i++) { $temp = 1 << $i; $flag = $temp & $value; if ($flag) { $result[] = $key * $int_bit_size + $i; //printf("value:%d i:%d temp 1<<%d=%d temp:%d flag:%d result:%d \n", $value, $i, $i, $temp, $temp, $flag, $key * $int_bit_size + $i); } //$num++; } } return $result; }
使用方法:
$data=getdata($bitmap);
判断数据是否存在:
function checkExists($bitmap, $val) { $int_bit_size = PHP_INT_SIZE * 8; $key = floor($val / $int_bit_size); $result = null; if (isset($bitmap[$key])) { for ($b = 0; $b < $int_bit_size; $b++) { $temp = 1 << $b; $flag = $temp & $bitmap[$key]; if ($flag && ($val == (($key * $int_bit_size) + $b))) { $result = $val; break; } // printf("value:%d b:%d key:%d temp:%d flag:%d\n", (($key * $int_bit_size) + $b), $b, $key, $temp, $flag); } } return $result; }
使用方法:
checkExists($bitmap, 999145);
动态添加:
function addData(&$bitmap, $val) { $int_bit_size = PHP_INT_SIZE * 8; $bytePos = floor($val / $int_bit_size); isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0; $bitPos = $val % $int_bit_size; $position = 1 << $bitPos; $bitmap[$bytePos] = $bitmap[$bytePos] | $position; return $bitmap; }
addData($bitmap,100); 向数组中添加一个100的数据
备注:
存储的数组中,数据不能重复,会替换。
例如说:
$arr = [5, 1, 7, 15, 0, 4, 6, 10, 14, 88, 15];
数组中有两个 15 ,只会保留一个 15,
且 getdata($bitmap)后,数据会从小到大依次排序
Array
(
[0] => 0
[1] => 1
[2] => 4
[3] => 5
[4] => 6
[5] => 7
[6] => 10
[7] => 14
[8] => 15
[9] => 88
)
只保留了一个15 ,且 顺序是从小到的 依次排序的。
这里还有一个功能就是可以做排序噢!
下面进行封装了一个类:
Bitmap.php
class Bitmap { public static $_instance = NULL; public $int_bit_size = NULL; private $_bitmap = []; public function __construct() { $this->int_bit_size = PHP_INT_SIZE * 8 - 1; } /** * 根据数组创建一个bitmap * @param $data * @param int $int */ public function createBitMap(array $data, $int = 10) { //创建一个指定长度以0填充的数组 $bitmap = array_fill(0, $int, 0); foreach ($data as $item) { //字节位置 $bytePos = $item / $this->int_bit_size; $bitPos = $item % $this->int_bit_size; $position = 1 << $bitPos; isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0; $bitmap[$bytePos] = $bitmap[$bytePos] | $position; } $this->_bitmap = $bitmap; return $this; } /** * 从小到大排序数组 * @param array $data * @return array */ public static function bitSort(array $data) { return (new self())->createBitMap($data)->getData(); } /** * 获取bitmap的原始数据 * @param $bitmap * @return array */ public function getData(array $bitmap = NULL) { $int_bit_size = $this->int_bit_size; $result = array(); $bitmap = is_null($bitmap) ? $this->_bitmap : $bitmap; foreach ($bitmap as $key => $value) { for ($i = 0; $i < $int_bit_size; $i++) { $temp = 1 << $i; $flag = $temp & $value; if ($flag) { $result[] = $key * $int_bit_size + $i; } } } return $result; } /** * 判断bitmap中是否存在这个数据 * @param $val * @return null */ public function checkExists($val) { if (!is_int($val)) return NULL; $int_bit_size = $this->int_bit_size; $key = floor($val / $int_bit_size); $result = NULL; if (isset(($this->_bitmap)[$key])) { for ($b = 0; $b < $int_bit_size; $b++) { $temp = 1 << $b; $flag = $temp & ($this->_bitmap)[$key]; if ($flag && ($val == (($key * $int_bit_size) + $b))) { $result = $val; break; } } } return $result; } /** * 在bitmap中添加数据 * @param $val * @return $this */ public function addData($val) { if (!is_int($val)) return $this; $int_bit_size = $this->int_bit_size; $bitmap = $this->_bitmap; $bytePos = floor($val / $int_bit_size); isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0; $bitPos = $val % $int_bit_size; $position = 1 << $bitPos; $bitmap[$bytePos] = $bitmap[$bytePos] | $position; $this->_bitmap = $bitmap; return $this; } /** * 在bitmap中删除一个数据 * @param $val * @return $this */ public function delData($val) { if (!is_int($val)) return $this; if ($this->checkExists($val)) { $int_bit_size = $this->int_bit_size; $key = floor($val / $int_bit_size); $bitPos = $val % $int_bit_size; $position = 1 << $bitPos; $new = $this->_bitmap[$key] & ~$position; $this->_bitmap[$key] = $new; } return $this; } /** * 获取bitmap的值 * @return array */ public function getBitmap() { return $this->_bitmap; } public function __get($name) { return $this->$name; } public function __set($name, $value) { $this->$name = $value; } }
//调用方法:
public function testAction() { $arr = [5, 1, 7, 15, 0, 4, 6, 10, 14, 88]; //$arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 99, 9, 10, 11, 12, 90, 13, 14, 15, 16, 17, 100, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 40, 50, 60]; $bitMap = new Bitmap(); $bitdata = $bitMap->createBitMap($arr)->getBitmap(); $ishave = $bitMap->checkExists(88); printf('数组中%s是否含有88 ::::: %s<br>', var_export($arr, TRUE), is_null($ishave) ? '无' : '有'); P($bitdata); printf('数组中%s是否含有77 ::::: %s<br>', var_export($arr, TRUE), is_null($bitMap->checkExists(77)) ? '无' : '有'); $bitMap->addData(77); printf('添加一个77<br>'); printf('数组中%s是否含有77 ::::: %s<br>', var_export($arr, TRUE), is_null($bitMap->checkExists(77)) ? '无' : '有'); printf('删除88<br>'); $bitMap->delData(88); printf('数组中%s是否含有88 ::::: %s<br>', var_export($arr, TRUE), is_null($bitMap->checkExists(88)) ? '无' : '有'); printf('获取原始数组<br>'); P($bitMap->getData()); //排序功能 //$sortData = Bitmap::bitSort($arr); //P($sortData); }
页面显示:
数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有88 ::::: 有 Array ( [0] => 50419 [1] => 0 [2] => 67108864 [3] => 0 [4] => 0 [5] => 0 [6] => 0 [7] => 0 [8] => 0 [9] => 0 ) 数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有77 ::::: 无 添加一个77 数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有77 ::::: 有 删除88 数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有88 ::::: 无 获取原始数组 Array ( [0] => 0 [1] => 1 [2] => 4 [3] => 5 [4] => 6 [5] => 7 [6] => 10 [7] => 14 [8] => 15 [9] => 77 )