专栏首页一Li小麦《javascript数据结构和算法》读书笔记(4):BitMap

《javascript数据结构和算法》读书笔记(4):BitMap

BitMap

引子

有n个整数,范围是[0,100]。试设计一种数据结构。储存这些数据,并提供两种方法。分别是

  • add
  • isExist

时间复杂度O(n)的实现

class FindClass{
    constructor(){
        this.datas=[]
    }

    add(item){
        this.datas.push(item)
    }

    isExist(item){
        return this.datas.indexOf(item)>=0;
    }
}

var a= new FindClass();
a.add(1)
a.add(2)
console.log(a.isExist(2))

复杂度的优化:活用索引值

不论是for循环还是indexof,元素越多,越慢。试实现时间复杂度为O(1)的算法。

改进add的逻辑:

class FindClass{
    constructor(){
        this.datas=new Array(100).fill(0)
    }

    add(item){
        this.datas[item]=1;
    }

    isExist(item){
        return this.datas[item]==1;
    }
}

var a= new FindClass();
a.add(1)
a.add(2)
console.log(a.isExist(2))

怎样更好节省内存:数据压缩

上面的操作把复杂度大大降低了。但是假设我存一亿个数,每个整数需要占用4个字节的空间。那么这个数组就占据381M的空间。如何通过合适的方法节省这么多的空间呢?

街边有8盏路灯,其中第2,5,7,8号是开着的。如何设计一种方法,表示这八盏灯的状态?

  • 2578,
  • 另外一种是75,转化为二进制就是=>01001011,刚好反映了路灯的状态。因此只要8个bit就可8盏灯的全部情况!

现在继续来看isExit。

value=00000000000000000000000000000000,add(0)存进来时,就把value的第 0位设为1

00000000 00000000 00000000 00000001

此时value实际为1(10进制)

如果add(3),就把value的第 3位设为1

00000000 00000000 00000000 00001001

此时value为9,因此9可以表示0和3都存在的状态。

同理我可以最多add(31)=>于是这个32位的二进制数value,可以表示0-31数字的存在与否。

如果我以一个长度为10的数组把value存起来。那么这个数据结构就能够支持add(319)的储存。

datas[0]=>支持31
datas[1]=>支持32=>63
...
data[9]=>支持最多319

因此,空间使用率为原来的1/32。

位运算

如何对整数的二进制位进行操作?这就是位运算的内容

按位与 &

相同二进制位的数字都为1时,则结果为1,否则为0

3&7=
3=>011
7=>111
结果=>011=>3
∴3&7=3

按位或 |

相同二进制位的数字有一个为1时,则结果为1,否则为0,实际上就是加法

5|8=5=>01018=>10005|8=>1101=>13

左移 <<

二进制向左移动n位,在后面加n个0

3<<1=
3=>11=110=6

以上运算优先级都是一致的。

练习

一组数为3,9,19,20,尝试以一个整数表示以上4位数.

var value=0;
value=value|1<<3
value=value|1<<9
value=value|1<<19
value=value|1<<20
console.log(value)//1573384

这里value|1表示1.1左移n位,换算为2^n

因此,这个整数的数学意义实际上是:2^3+2^9+2^19+2^20=1573384

console.log(Math.pow(2,3)+Math.pow(2,9)+Math.pow(2,19)+Math.pow(2,20))

BitMap的实现

来实现真正的BitMap吧!

回到需求,4个整数足以放表示128个数的存在状态。(长度为4的数组);

根据item的范围用求模的方式获取index。

class FindClass{
    constructor(){
        this.datas=new Array(4).fill(0)
    }

    add(item){
        let arr_index=parseInt(item/32);//确定所在数组索引
        let bit_index=item%32;//确定二进制位移
        let value=this.datas[arr_index];
        value=value|1<<bit_index;
        this.datas[arr_index]=value;
    }

    isExist(item){
        // 检验对应位数
        let arr_index=parseInt(item/32);//确定所在数组索引
        let bit_index=item%32;//确定二进制位移
        let value=this.datas[arr_index]&1<<bit_index;
        return value!==0 ;//实际上就是1
    }
}

var a= new FindClass();
a.add(1)
a.add(2)
console.log(a.isExist(2))//true
console.log(a.isExist(3))//false

以上数据结构基于位操作作为映射,能够以很少的内存去操作数据(只能表示某个数存在)。最大值支持15亿的集合。可以用于大数据去重,大数据排序。两个集合取交集。等等。

应用

大数据排序

比如:有多达10亿个的无序整数,最大值为15亿,请对这10亿个数进行排序

为了简化这个思路。现将数组转化为:

var arr=[0,6,88,7,73,34,10,99,22]//最大99
var bit_map= new FindClass();
for(let i=0;i<arr.length;i++){
    bit_map.add(arr[i])
}
var sort_arr=[];
for(let i=0;i<99;i++){
    if(bit_map.isExist(i)){
        sort_arr.push(i)
    }
}
console.log(sort_arr)//[ 0, 6, 7, 10, 22, 34, 73, 88 ]

缺陷是:不能有重复数据。如果数据很少差异太大,那么就空间利用率就太低了。

布隆过滤器

如果你写了一个强大的爬虫程序,每天可以爬取数以亿计的url。那么你需要一个结构,存储他们,同时才不至于重复爬取。

哈希函数

一个思路在于用hash函数对url进行处理。

他可以把一个不定长的对象转化为定长的对象。在题目中,是转化为定长的整数。

但是哈希函数可能会超过最大映射值M,同时转换可能产生冲突。

一次不靠谱

扩展

布隆过滤器实际上是bitmap的扩展。

为了解决冲突,布隆过滤器要求使用k个hash函数,新增一个key时,把key散列为k个整数。

然后在数组中将这k个整数所对应的二进制位数设置为1

如果判断key是否存在,还是对key进行散列。判断对应的整数位数是否都为1,如果是,这个key就存在了。

对于布隆过滤器,需要设置两个参数,一个是最大熟练n,一个是容忍的冲突率p。那么可以求得k值:

m=-(n*(ln^p))/((ln2)^2)
k=(ln^2)*(m/n)

下面就来实现吧

class BoolmFilter{
    constructor(max_count,error_rate){
        this.bit_map=[]//位图映射变量
        this.max_count=max_count;//最多可存放的数量
        this.error_rate=error_rate;//错误率
        this.bit_size=Math.ceil(this.max_count*(-Math.log(this.error_rate)/(Math.log(2)*Math.log(2))));//变量长度
        this.hash_count=Math.ceil(Math.log(2)*(this.bit_size/this.max_count))//哈希数量
    }
    //把key散列为k个值
    set_bit(bit){
        let arr_index=Math.floor(bit/32);
        let bit_index=Math.floor(bit%32);
        this.bit_map[arr_index]|=(1<<bit_index);
    }
    // 读取位的值
    get_bit(bit){
        let arr_index=Math.floor(bit/32);
        let bit_index=Math.floor(bit%32);
        return this.bit_map[arr_index]&=(1<<bit_index)
    }

    add(key){
        if(this.isExist(key)){
            return -1
        }

        for(let i=0;i<this.hash_count;i++){
            // 获取哈希,传不同的种子(i)
            let hash_value=murmurhash3_32_gc(key,i);
            this.set_bit(Math.abs(Math.floor(hash_value%(this.bit_size))));
        }
    }
}

本文分享自微信公众号 - 一Li小麦(gh_c88159ec1309),作者:一li小麦

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 组件设计基础(2)

    早期的react设计了许多的生命周期钩子。它们严格定义了组件的生命周期,一般说,生命周期可能会经历如下三个过程:

    一粒小麦
  • react的前端验证码

    完整代码: https://github.com/dangjingtao/vccode效果预览

    一粒小麦
  • 虚拟滚动之原理及其封装

    前端的业务开发中会遇到一些不分页且数据条数超过1000加载的列表(长列表),不分页的需求在一般前端程序员看来是不可思议的。正常的思考逻辑是,当数据量20w+时,...

    一粒小麦
  • 不打开Wifi获取Mac地址

    今天遇到一个问题,要求不打开Wifi的前提下获取Mac地址,所以针对Android上Mac地址的获取做了总结。 MAC地址:每个接入网络的设备都有一个专门的序...

    用户7557625
  • Sql Server 集合防黑办法

    Sql Server 中将由逗号“,”分割的一个字符串,转换为一个表,并应用与 in 条件查询一个集合基本上多数据查询的必备项目.

    谭广健
  • JDK1.8 LinkedList 源码解析

    tanoak
  • JavaScript 五种基本数据类型(上)

    城市中的游牧民族
  • 嵌入式面试题(一)

    4. 空指针(null pointer)指向了内存的什么地方(空指针的内部实现)?

    Daotin
  • xslt notes:数值函数与字符串函数

    落叶大大
  • 4.信号量 原

    (adsbygoogle = window.adsbygoogle || []).push({});

    青木

扫码关注云+社区

领取腾讯云代金券