Blackops

初心易得，始终难守

0%

压缩存储BitMap简单入门

发表于 分类于

核心思想

把数字”哈希”到某一个位置$x$，然后将这个位置标为$1$，代表这个映射位置有值存在了。关键在于如何”哈希”？我的理解是先将数字分到某一块，再把余数作为映射位置（有点像Cache的组相联映射）。

压缩公式：$x = i*B+j$，$0\le j \lt B$，$B$为用于压缩存储的数字的最大位数，那么$i$就是压缩后存储的块，$j$就是该块中标记$x​$存在的位置

举个例子，现在将579这个数字放入BitMap，那么$579=18*32+3​$，让BitMap[18]的第3位为1即可。代码就是bit[579 >> 5] |= (1 << (579 & 31));
查询操作，就是将查询的数按上述公式分解，去查对应位是否为1即可。
取数操作，就是遍历所有的BitMap[i]，若某一位j为1，则说明存在。

压缩效率简单分析

假设我们用M位二进制的整数去存N个数字，那么实际上每一个数字最多压缩后占1位，最佳情况只需N/M个整数作为BitMap，因此假如用32位的int，1e9的数字只用3e7+的数字去存储。压缩倍数为$B$倍

局限性

由于位运算只能有0和1的状态，因此重复的数据只能算一个。

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) emplace_back(x)
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define fl(i,f_start,f_end) for(int i=f_start;i<f_end;++i)
#define fe(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 110;
struct BitMap
{
    int bit[N];
    void init() {
        clr(bit, 0);
    }
    void insert(int x) {
        bit[x >> 5] |= (1 << (x & 31));
    }
    int query(int x) {
        return bit[x >> 5] & (1 << (x & 31));
    }
    vector<int> getall() {
        vector<int>ret;
        fl(i, 0, N) {
            fl(j, 0, 32) {
                if (bit[i] & (1 << j)) {
                    ret.pb((i << 5) + j);
                }
            }
        }
        return ret;
    }
} bitmap;

void show(vector<int> v)
{
    fl(i, 0, v.size())
    {
        printf("%d%c", v[i], " \n"[i == (int)v.size() - 1]);
    }
    puts("");
}

int main(void)
{
    int testnum = 10;
    //生成testnum个随机数用于测试
    vector<int>test;
    srand(time(NULL));
    fl(i,0,testnum)
        test.pb(rand() % N);
    sort(all(test));//排个序便于观察

    show(test);
    fl(i, 0, testnum)
    	bitmap.insert(test[i]);
    show(bitmap.getall());

    return 0;
}