,## 基础知识储备
一个字节占用8个位
1字节(byte)=8位(bit)
1K=1024字节
1M=1024k
因为电路的逻辑只有0和1两个状态,这里的0和1并不是数字的0和1,0和1是表示两种不同的状态,0表示低电平,1表示高电平。因为计算机是由无数个逻辑电路组成的,只能根据0和1的无限位数和组合来表达信息。 电脑只认识0和1这两个数字,所有的数据在电脑中都是以0和1组成的编码存储的,这样的编码叫做二进制。一个0或一个1就叫做一个位 最初的计算机性能和存储容量都比较差,所以普遍采用4位BCD编码(这个编码出现比计算机还早,最早是用在打孔卡上的)。 BCD编码表示数字还可以,但表示字母或符号就很不好用,需要用多个编码来表示。 后来又演变出6位的BCD编码(BCDIC),以及至今仍在广泛使用的7位ASCII编码。 不过最终决定字节大小的,是大名鼎鼎的System/360。当时IBM为System/360设计了一套8位EBCDIC编码,涵盖了数字、大小写字母和大部分常用符号,同时又兼容广泛用于打孔卡的6位BCDIC编码。System/360很成功,也奠定了字符存储单位采用8位长度的基础,这就是1字节=8位的由来。
位运算
位运算就是直接对整数在内存中的二进制位进行操作。 上面已经介绍了什么是二进制位,数字1的二进制位为 00000001
数字2的二进制位为 00000010
例子
说明
名称
$a & $b
将把 $a 和 $b 中都为 1 的位设为 1。
按位与
$a 丨 $b
将把 $a 和 $b 中任何一个为 1 的位设为 1。
按位或
$a ^ $b
将把 $a 和 $b 中一个为 1 另一个为 0 的位设为 1。
- 按位异或
- $a
将 $a 中为 0 的位设为 1,反之亦然。
按位取反
$a << $b
将 $a 中的位向左移动 $b 次(每一次移动都表示“乘以 2”)。
左移
$a >> $b
将 $a 中的位向右移动 $b 次(每一次移动都表示“除以 2”)。
右移
这里只拿& 和 简单介绍,其他的可以在官网手册进一步学习。
<?php
$a = 1;
$b = 2;
echo $a & $b; // 结果0
// $a => 00000001
// $b => 00000010
// ↓ 同一个位都为1的才设为1
// => 00000000
<?php
$a = 1;
$b = 2;
echo $a $b; // 结果3
// $a => 00000001
// $b => 00000010
// ↓ 任何一个位为1的就设为1
// => 00000011
php中int类型占用多少字节
var_dump(PHP_INT_SIZE); // 表示整数integer值的字节长。在32位平台上int占4个字节,在64位平台上int占8个字节。
以下场景均为使用64位平台
在php中,一个int类型的值占用的位数为:
PHP_INT_SIZE * 8 = 8 * 8 = 64
bitmap算法
bitmap
从字面意思是位图,但是在这里,我们应该翻译成 位的映射
BitMap算法就是用一个bit位来标记某个元素存在,该bit位所在的key就是该元素的值。 如我们需要储存一组数据:3,6,7,1,5 我们可以声明一字节空间(8个位) 然后分别将第3位、第6位、第7位、第1位、第5位的bit值设置成1
位的下标是从0开始算的
于是这一字节空间就变成了 010100110
本来是5个int,占用 40个字节,用bitmap储存只占用了 1个字节
储存完后 也可以达到排序的效果,只要遍历一次,从第0位开始读取是否为1,这样就能拿到5个元素排序后的结果。
用途
- 数据压缩储存
- 通过位运算对比筛选储存数据
- 数据去重排序
优点
- 占用内存少 压缩储存数据
- 可进行快速方便的位运算
- 快速查找使用
- 快速排序去重
缺点
- 无法处理重复数据
- bitmap中的查询结果(value)能表达的状态有限
php实现
<?php
# 定义一个数据 开辟储存空间
$arr = array_fill(0, 50, 0); //申请一个整形数组, 50个元素, 初始化为整数0
$int_bit_size = PHP_INT_SIZE * 8; // 每一个int占用的位数 (可储存标记的数量)
$a = array(1,2,3,6,6,7,9,1,11,105,97,31,66,58,69,25); // 乱序数组
foreach ($a as $k => $v){
$row = (int) floor ($v / $int_bit_size); // 数据储存在第几行
$wei = $v % $int_bit_size; // 数据储存在第几位
// 以下看不懂的 请看文章开头的 知识储备 位运算
$offset = 1 << $wei; // 1是 00000001 ; 得到的余数 (位) 假设为3 则左移3位 得到 00001000
$arr[$row] = $arr[$row] $offset; // 将位改为1 标记储存数据
}
演习就是实战
需求:用户属性标签。 Siam拥有程序员、画画标签;仙士可拥有程序员、奶爸、有老婆标签。 Siam弟弟的做法:以用户为单位,储存标签。 用户表
u_id
u_name
u_tags
1
Siam
1,2
2
仙士可
1,3,4
标签表
tag_id
tag_name
1
程序员
2
画画
3
奶爸
4
有老婆
嗯 看起来好像没什么毛病 查询出u_tags再分割查询tag 正常显示 新需求来了 在后台 统计分析 拥有某个标签的用户数量 what the f*ck?
emmmm… 新版用户表
u_id
u_name
age
job
…
1
Siam
20
程序员
…
2
仙士可
NULL
程序员
…
能统计了…但是?? 每个标签都要预先创建好列
思维转换 新版标签表 用户表还是用第一版
tag_id
tag_name
tag_users
1
程序员
1,2
2
画画
1
3
奶爸
2
4
有老婆
2
如果直接以这样子的数据储存用户id,当用户量多了,数据就会非常的大,做分析的时候,占用了很多内存, 我们把tag_users字段的储存,用bitmap算法,压缩储存
<?php
$arr = []; // 如果是做更新操作 原数组从储存中拿出
// 先运算用户id在第几行和第几位 (一行是一个int,64位)
$bitSize = PHP_INT_SIZE * 8;
$uId = 100;
$row = (int) floor ( $uId / $bitSize );
$column = $uId % $bitSize;
$offset = 1 << $column;
$arr[$row] = $arr[$row] $offset;
echo json_encode($arr); // 将json存入db
除了压缩储存的优势,在做用户群交集并集运算的时候,bitmap也有极大的便利优势。
数据取出筛选分析 (位运算)
以下代码比较多 请用心看完!
<?php
// 先分别从db取出数据 伪代码
$bitSize = PHP_INT_SIZE * 8;
// 程序员
$programmer = [
0 => '6', // 00000110 储存了用户1、2
1 => '2199023255552', // 储存了用户105
];
// 画画
$draw = [
0 => '2', // 00000010 储存了用户1
1 => '2199023255552', // 储存了用户105
];
// 有老婆的
$notSingleDog = [
0 => '4', // 00000100 储存了用户2
1 => '0',
];
// 奶爸
$father = [
0 => '4', // 00000100 储存了用户2
1 => '0',
];
/**
* 会画画的程序员 交集
*/
$tem = [];
// 遍历程序员 看看哪些会画画
foreach ($programmer as $key => $value){
// 这里的一个key 等于一行 value是bitmap
$tem[$key] = $value & $draw[$key];
}
// 得到交集的bitmap 再解析成u_id
$uId = [];
foreach ($tem as $k => $v){
for ($i=0; $i < $bitSize; $i++)
{
$tmp = 1 << $i;
$flag = $tmp & $tem[$k];
if ($flag) {
$uId[] = $k * $bitSize + $i;
}
}
}
echo "会画画的程序员:<br/>";
var_dump($uId);
/**
* 有老婆的程序员 交集
*/
$tem = [];
foreach ($programmer as $key => $value){
$tem[$key] = $value & $notSingleDog[$key];
}
$uId = [];
foreach ($tem as $k => $v){
for ($i=0; $i < $bitSize; $i++)
{
$tmp = 1 << $i;
$flag = $tmp & $tem[$k];
if ($flag) {
$uId[] = $k * $bitSize + $i;
}
}
}
echo "有老婆的程序员:<br/>";
var_dump($uId);
/**
* 有老婆又会画画的程序员 交集
*/
$tem = [];
foreach ($programmer as $key => $value){
$tem[$key] = $value & $notSingleDog[$key] & $draw[$key];
}
$uId = [];
foreach ($tem as $k => $v){
for ($i=0; $i < $bitSize; $i++)
{
$tmp = 1 << $i;
$flag = $tmp & $tem[$k];
if ($flag) {
$uId[] = $k * $bitSize + $i;
}
}
}
echo "有老婆又会画画的程序员:<br/>";
var_dump($uId);
/**
* 有老婆或者会画画的程序员 并集
*/
$tem = [];
foreach ($programmer as $key => $value){
$tem[$key] = $value & ($notSingleDog[$key] $draw[$key]);
}
$uId = [];
foreach ($tem as $k => $v){
for ($i=0; $i < $bitSize; $i++)
{
$tmp = 1 << $i;
$flag = $tmp & $tem[$k];
if ($flag) {
$uId[] = $k * $bitSize + $i;
}
}
}
echo "有老婆或者会画画的程序员:<br/>";
var_dump($uId);
会画画的程序员:<br/>array(2) {
[0]=>
int(1)
[1]=>
int(105)
}
有老婆的程序员:<br/>array(1) {
[0]=>
int(2)
}
有老婆又会画画的程序员:<br/>array(0) {
}
有老婆或者会画画的程序员:<br/>array(3) {
[0]=>
int(1)
[1]=>
int(2)
[2]=>
int(105)
}
然而 bitmap算法也存在着缺点:不能直接进行非运算
如,想要获取不是程序员的用户数量,如果直接拿程序员标签的结果进行非运算,并不会得到准确的用户信息, 假设声明了一个64位的空间,其中只有3个用户是程序员,占用了1/2/3位,如果直接运行非运算,将会得到0/4/5/6…/63位的数据 但我们的系统可能没有64个用户,或者用户的id进行了跳跃,并不是连续的,所以得到了错误的列表。 我们需要借助全量用户的bitmap。 每有用户注册,不管他设置了什么标签,都需要往全量bitmap进行插入,这样子就可以用全量bitmap和程序员标签的bitmap进行运算,得到非程序员用户
的列表
扫描二维码,分享此文章