1.稀疏数据的例子

  对于网络图对应的节点关联矩阵、数据生成的哈希表,这些存储起来是稀疏的,这样我们就会想到需要压缩空间。但是在压缩存储空间的同时,还要支持高效的查询操作。

  Rank & Select 就可以对稀疏的数据进行压缩,还能支持高效的查询操作。

2.Rank & Select 操作压缩稀疏数据原理

  以下图为例子,假如是经过哈希后得到的哈希数组:

  

  构造数组A和B:

    Vec-A:1010100110001    (每个位置一个比特位,1:有数据,0:无数据)

     Num-B:12  2  23  11  12  1  (数据按原来的相对顺序,保存为一个数组)

  (1)Rank:

    针对Vec-A数组而言,记录每个位置前面(包括本位)有多少个1,也就是对应之前有多少个有效数字。这样做的目的是使得,数组中的有效数字的排名与在Num-B中的位置一致。

  (2)Select:

    根据查询数据在Vec-A上面的Rank排名,在Num-B中查询数据。

  (3)Rank & Select

    

    eg1:位置4对应的位置没有数据,所以在Vec-A中标记为0;

    eg2:位置5对应的位置有数据23,所以在Vec-A中标记为1。Vec-A(5)对应的rank为3,说明包含自己在内之前一共有3个数据,且在位置5对应的数据保存在Num-B的第3为,即Select(5)=Num-B(Rank(5))

4.使用SSE指令高效计算Rank

  SIMD,单指令多数据,就是一条指令由多个执行单元同时并行执行操作多个数据

  SSE是指令集的简称,它包括70条指令,其中包含SIMD浮点计算、以及额外的SIMD整数和高速缓存控制指令。就是说SSE中存在指令,是SIMD指令,使得多核CPU可以高效执行。

  SSE指令 int _mm_popcnt_u32 (unsigned int a); 返回32为无符号整形 a 中bit位为1的位的个数。

5.Rank & Select 简单示例

  实例程序就是上面图中的例子,13个位置(1,2,3,..,14),6个有效位置。对其进行使用rank & select,进行压缩、并支持查询。

  例子较小,没有使用SSE指令,只是对rank select操作的简单说明。

 1 #include <iostream> 
 2 #include <string.h> 
 3 #include <bitset> 
 4 using namespace std; 
 5  
 6 /** 
 7 设置原始数组num以及设置对应在ver_A的比特位 
 8 num:保存原始数据的数组 
 9 n:数组大小 
10 ver_A:标记有效数字位向量 
11 */ 
12 int initNumVer(int *num,int *ver_A,int n){ 
13     memset(num,0,sizeof(int)*n); 
14     num[1] = 12;    *ver_A |= (1<<1); 
15     num[3] = 2;     *ver_A |= (1<<3); 
16     num[5] = 23;    *ver_A |= (1<<5); 
17     num[8] = 11;    *ver_A |= (1<<8); 
18     num[9] = 12;    *ver_A |= (1<<9); 
19     num[13] = 1;    *ver_A |= (1<<13); 
20     return 0; 
21 } 
22  
23 /** 
24 ver_A:位向量 
25 rank:排名 
26 num_B:压缩后的数组 
27 pos:要查的位置 
28 */ 
29 int query(int *ver_A,int *rank,int *num_B,int pos){ 
30     if((*ver_A&(1<<pos)) == 0) 
31         return 0; 
32     else 
33         return num_B[rank[pos]]; 
34 } 
35  
36 int main (){ 
37     const int n = 14; 
38     int  ver_A = 0; 
39     int *num = new int[n]; 
40     int *rank = new int[n]; 
41     int *num_B = new int[7];    ///例子中有效数字6个,num_B[0]不使用 
42  
43     ///设置原始数组num以及设置对应在ver_A的比特位 
44     initNumVer(num,&ver_A,14); 
45  
46     ///设置rank与压缩后的数组num_B 
47     for(int i=0,j=0;i<n;i++){ 
48         if( (ver_A&(1<<i)) != 0) 
49             num_B[++j] = num[i]; 
50         rank[i]=j; 
51     } 
52  
53     ///查询第4、5个数 
54     cout<<"第4个数:"<<query(&ver_A,rank,num_B,4)<<endl; 
55     cout<<"第5个数:"<<query(&ver_A,rank,num_B,5)<<endl; 
56  
57     delete [] num; 
58     delete [] rank; 
59     delete [] num_B; 
60     return 0; 
61 }
View Code

6.注意

  (1)程序中以一维数组为例,其实多维数组也是连续存储,也可以理解为“一维数组”。

  (2)SSE指令时间复杂度为O(1),但是SSE指令操作位数有限。

  (3)如果Vec-A比特向量很长时,可以先计算一些rank数据保存下来(空间换时间),也可以达到计算任意位置rank操作时间复杂度为O(1)。

 

发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

树状数组(Binary Indexed Tree) 总结讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。