BitMap JS实现以及重复数检查

BitMap JS实现以及重复数检查

Tags
二进制编程
JavaScript
位图算法
CreatedTime
Aug 19, 2022 10:37 AM
Slug
2021-08-08-bitmap-js
UpdatedTime
Last updated August 19, 2022

位图(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://0x98k.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 byteLengh = 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. 依次扫描整数
  1. 扭转整数对应的 2 个 bit 位的状态,00 变成 01,01 变成 11,11 不需要变
  1. 重新遍历所有的 bit 位,找到 bit 位为 01 对应的数字即可

参考