Siam博客

bitmap算法的PHP实现,快速去重排序,数据压缩储存

2019-08-30

,## 基础知识储备

一个字节占用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进行运算,得到非程序员用户的列表

本文链接:
版权声明: 本文由 Siam原创发布,转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权

扫描二维码,分享此文章