位图学习

算法 C++, 大数据存储 评论

已知a.txt中有40亿个无符号整数，b.txt中有10000个无符号整数，求交集。可用内存：1G

定义

位图法是bitmap的缩写，其指用每一位来存放某种状态，适用于大规模数据，但数据状态不多的情况
举例说明：

1
unsigned int bit[N];

在该数组成可存储N*sizeof(int)8个数据，但最大的数只能是Nsizeof(int)*8-1。若存数据范围0~15，则使N=1即可
位图举例
数据为【5，12，1，0，4】存入后：
位图举例2

使用范围

使用bit数组来表示某些元素是否存在，如8位电话号码等

位图的操作

在C++中int类型由4个字节，即32位。当有1000万条不同数据时，我们只需1000万个位来表示，也就是10000000/(8*1024*1024)MB，约为1.25MB
1MB=1000KB=10^6B—–百万字节
1GB=1000MB=10^9B—–十亿字节
1000万条=10^7=(10/8)*10^6 B=1.25MB

使用一个unsigned int类型的数组或向量来表示位图，假定vectora，则第i为可表示为a[i/32]的i%32位（其中，32*N+r=i）

i/32使用位移操作：i>>5，i%32使用：i&31

  • setZero置零操作
    将位图中第i位置零

    1
    a[i>>5] &= ~(1<<(i&31));

  • setOne置位操作
    将位图中的第i位设置为1，即将a[i/32]的第（i%32）位设置为1。

    1
    a[i>>5] |= (1<<(i&31));

  • getState获取状态操作
    判断第i位是否为1，得到的值大于0，说明该位值为1，否则为0

    1
    return a[i>>5] &(1<<(i&31));

实现代码

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
#include<iostream>
#include<fstream>
using namespace std;
#define BIT_INT 32
#define SHIFT 5
#define MASK 0x1f
#define N 4294967296
unsigned int *a = NULL;
void createALL(){
	a = new unsigned int[1+N/BIT_INT];
}
void deleteALL(){
	delete[] a;
    a = NULL;
}
void SetAllZero(){
	memset(a,0,(1+N/BIT_INT)*sizeof(unsigned int));
}
void setOne(unsigned int i){
	a[i >> SHIFT] |= (1<<(i&MASK));
}
void setZero(){
	a[i >> SHIFT] &= ~(1<<(i&MASK));
}
int getState(unsigned int i){
	return (a[i >> SHIFT] &(1 << (i&MASK)));
}
void setStateFromFile(){
  ifstream cin("a.txt");
  unsigned int n;
  while(cin>>n){
    setOne(n);
  }
}
void printCommonNumber(){
  ifstream cin("b.txt");
  unsigned int n;
  while(cin>>n){
    if(1 == getState(n))
      cout<<n<<" ";
  }
  cout<<endl;
}
int main(){
  createALL();
  SetAllZero();
  setStateFromFile();
  printCommonNumber();
  deleteALL();
  return 0;
}

函数库实现

C++的STL中有bitmap类，它提供了很多方法，详见http://www.cplusplus.com/reference/stl/bitset/

  • 使用C++的bitset:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<bitset>
using namespace std;
#define N 10000000
bitset<N> b;
int main(){
  int n;
  while(cin>>n){
    b.set(n);
  }
  for(int i = 0;i < N;i ++){
    if(b.test(i)){
      cout<<i<<endl;
    }
  }
}

注意：
bitset不能放在main内，否则stack overflow。若要放在main内，要放在main内，要加static或new一个。

位图应用

  • 求字符的所有组合

思路：输入a、b、c,则它们的组合为a,b,c,ab,ac,bc,abc。

假设原有元素有n个，则最终组合为2^n-1个。利用位图思想，假设原有a、b、c三个元素，则1表示取元素，0表示不取。故取a则为001，取ab则为011，而000没有意义，所以共有2^n个结果。
这些位图值都是1,2,…,2^n,所以从值1到值2^n-1的输出结果为：
001,010,…,111
对应观察结果为：a,b,ab,c,ac,bc,abc。
因此，循环1~2^n-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
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
void combination(string str) {
	if (str == " ")
	{
		return;
	}
	int len = str.length();
	int n = 1 << len;
	for (int i = 0;i < n;i++ )
	{
		for (int j = 0;j < len;j ++)
		{
			int temp = i;
			if (temp &(1 << j))
				cout << str[j];
		}
		cout << endl;
	}
}
int main(){
	string str = "abc";
	combination(str);
	system("pause");
	return 0;
}
  • bitmap求哈密尔顿距离

问题描述
给定N（1<=N<=100000）个五维的点(X1,X2,X3,X4,X5)，求两点X(x1,x2,x3,x4,x5)和Y(y1,y2,y3,y4,y5)使得|x1-y1|+|x2-y2|+|x3-y3|+|x4-y4|+|x5-y5|最大

  • 解题思路

对于任意两点(x1,x2)和(y1,y2)

|x1-y1|=max(x1-y1,y1-x1);
=>|x1-y1|+|x2-y2|=max{
(x1-y1)+(x2-y2)
(x1-y1)-(x2-y2)
(y1-x1)+(x2-y2)
(y1-x1)-(x2-y2)
};

=max{
(x1+x2)-(y1+y2)
(x1-x2)-(y1-y2)
(-x1+x2)-(-y1+y2)
(-x1-x2)-(-y1-y2)
};

通过观察，发现每一对相同元的符号必定相反，如：xi-yi，于是使用bitmap的思想来枚举这些二维的点的x轴和y轴前的正负号，这样可用一个0~3的二进制形式来表示：0表示+号，1表示-号。

对于每个点X和Y的符号，可用A[4]数组存储下来，那么对于点1(x1,y1)和2(x2,y2)两点就可表示为下式一：

A[1][0] - A[2][0]
A[1][1] - A[2][1]
A[1][2] - A[2][2]
A[1][3] - A[2][3]

约定X[ij]的下标数字(ij)是二进制，令

X00=x1+x2
X01=x1-x2
X10=-x1+x2
X11=-x1-x2

假设有A-Z共26个点，则
result=max{
(A00-B00), (A01-B01), (A10-B10), (A11-B11),
(A00-C00), (A01-C01), (A10-C10), (A11-C11),
……
(X00-Y00), (X01-Y01), (X10-Y10), (X11-Y11),
(Y00-Z00), (Y01-Z01), (Y10-Z10), (Y11-Z11),
}

很明显，对上面每一列应用max运算：

max(第一列)=
max(A00,B00,…,Z00) - min(A00,B00,…,Z00)

result=max{max(第一列)，max(第二列) … };

对每个I(00,01,10,11)，求A[*][I]的最大值max(I)和最小值min(I),然后再求max{max(I)-min(I)}

  • 通俗的理解

先求A[i][I]-A[j][I](I=00,01,10,11)，还原就是先求该等式xi+xj-(yi+yj)的最大值,分解后变成求max(xi+xj)和min(yi+yj)。再求这两个数相差后得到的集合中的最大值即可。

代码实现

总结

wonderxiaoNetwork Enginner & Designer

网络工程师