文章目录加载中

JavaScript-位图

# 位图(bitmap)介绍

什么是位图?

用 1 个(或多个)bit 位,来表示某个值。

位图的好处?

1、使用 bit 位,相较于使用原生数据结构,占用内存更少。

例如,对于 0、6 这 2 个数字,一个 int 类型的数字,是 4 个字节,也就是 2*8=16 个 bit 位。如果用 bitmap 表示呢?只需要申请一个字节,一个字节有 8 个 bit 位,初始全部置 0,从最低位到最高位分别对应数字 0-7,如果数字存在,那么 bit 位置 1,所以 0、6 对应的字节是:0100 0001

2、更容易进行集合运算。例如要求 2 个集合的交集,一个是{0, 6, 7},一个是{2, 4, 6}。那么只需要将他们用 bitmap 表示,然后将 bit 位进行&运算,并且将得到的 bitmap 转换为对应数字即可。

位图的缺点?

一般来说,假设要表示的数据集合的容量是n,那么申请的 bit 位是10*n。对于范围过大的数字,单纯用 bitmap 反而需要申请更多空间,可以使用“布隆过滤器”。

# 应用 1: 位图实现 BitSort

使用 js 实现了 bitmap,并且实现 bitsort 排序算法:

/*
 * @Author: dongyuanxin
 * @Date: 2020-12-27 16:26:18
 * @Github: https://github.com/dongyuanxin/blog
 * @Blog: https://xin-tan.com/
 * @Description: js位图
 */

const BYTE_SIZE = 8; // 1byte = 8bit

/**
 * 位图的实现
 */
class BitMap {
  constructor(bytes = 0) {
    this.buf = Buffer.alloc(bytes); // 申请bytes个字节大小
  }

  /**
   * 作用:将第position个数对应的字节位,设置为1
   * 思路:最简单的8个bit可以表示[0, 7]共8个数字,分别是:
   *   0000 0001(表示0)
   *   0000 0010(表示1)
   *   ......
   */
  set(position) {
    let index = Math.floor(position / BYTE_SIZE);
    let offset = position % BYTE_SIZE;
    // 对应的字节的bit位置位0
    this.buf[index] = this.buf[index] | (0x01 << offset);
  }
}

function bitSort(nums = []) {
  // step1: 计算需要的字节数
  const byteLength = Math.ceil(nums.length / BYTE_SIZE);
  // step2: 生成对应字节数的位图,并将出现的数字的bit位标识为1
  const bitmap = new BitMap(byteLength);
  nums.forEach(num => bitmap.set(num));
  // step3: 遍历所有的字节,找到为1的所有bit位对应的所有数字
  for (let i = 0; i < byteLength; ++i) {
    let mask = 0x01; // 掩码
    let j = 0; // 标识当前字节的bit位
    do {
      // step3.1: 找到为1的bit位,将其转换为对应的数字
      if ((bitmap.buf[i] & mask) === mask) {
        const num = i * BYTE_SIZE + j;
        process.stdout.write(num.toString() + " ");
      }
      // step3.2: 移动掩码,继续查找下一个bit位
      mask = mask << 1;
      ++j;
    } while (j < BYTE_SIZE);
  }

  process.stdout.write("\r\n");
}

// 测试代码:bitsort排序
// 输出:2 3 5 6 8 9 10 12 14
bitSort([3, 5, 2, 10, 6, 12, 8, 14, 9]);

# 应用 2: 找到 2.5 亿个整数中不重复的数

假设:内存不足以容纳这 2.5 亿个整数。直接申请数组或者使用哈希表肯定不可行。

借助 bitmap 的思路,可以用 bit 位来表示数组的出现情况。根据要求,有 3 种情况:

  • 没出现过
  • 出现过 1 次
  • 出现过多次

由于是 3 种情况,所以需要 2 个 bit 位,3 种情况对应 bit 位是:

  • 00
  • 01
  • 11

那么思路大体就是:

  1. 依次扫描整数
  2. 扭转整数对应的 2 个 bit 位的状态,00 变成 01,01 变成 11,11 不需要变
  3. 重新遍历所有的 bit 位,找到 bit 位为 01 对应的数字即可

# 参考

本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog