当前位置:天才代写 > tutorial > 大数据教程 > 数据结构之位图

数据结构之位图

2021-02-23 15:02 星期二 所属: 大数据教程 浏览:8

1.  简述

位图文件(bitmap)是一种十分常见的构造,在数据库索引,数据编码等层面有广泛运用。文中详细介绍了位图文件的完成方式以及应用领域。

2. 位图文件完成

(1)自身完成

当政图上,每一个原素为“0”或“1”,表明其相匹配的原素不会有或是存有。

#define INT_BITS sizeof(int)
#define SHIFT 5 // 2^5=32
#define MASK 0x1f // 2^5=32
#define MAX 1024*1024*1024 //max number
int  bitmap[MAX / INT_BITS];
/*
* 设定第i位 
* i >> SHIFT 等同于 i / (2 ^ SHIFT),
* i&MASK等同于mod实际操作 m mod n 计算
*/
void  set(int  i) {
  bitmap[i >> SHIFT] |= 1 << (i & MASK);
}
//获得第i位
int  test(int  i) {
  return  bitmap[i >> SHIFT] & (1 << (i & MASK));
}
//消除第i位
int  clear(int  i) {
  return  bitmap[i >> SHIFT] & ~(1 << (i & MASK));
}

(2)库函数完成

C 的STL中有bitmap类,它出示了许多 方式,详细:http://www.cplusplus.com/reference/stl/bitset/

3.  位图文件运用

3.1    枚举类型

(1)全组成

字符串数组全组成枚举类型(针对长短为n的字符串数组,组成方法有2^n种),如:abcdef,能够结构一个从字符串数组到二进制的投射关联,根据枚举类型二进制来开展全排列。

null——> 000000

f——> 000001

e——> 000010

ef——> 000011

……

abcedf——> 111111

(2)哈米尔顿间距

枚举算法,复杂性是O(N^2),如何减少复杂性呢?

如果是N 个二维的点,那麼我们可以如何使用迅速的方式求出

根据简易的数学课形变,我们可以获得那样的公式:

仔细观察,大家发觉每一对同样元的符号必然反过来,如:x_i-y_i,因此大家拥有一个二进制观念的构思,那便是枚举类型这种二i维的点的x 轴y 轴前的绝对值符号,那样就可以用一个0~3 的数的二进制方式来表明每一个原素前边的绝对值符号,1表明 号,0表明−号,如:2 表明的二进制位方式为10表明x_i-y_i。那样大家就可以根据2^2*N次纪录下这种二元组的不一样的标记的标值,针对每一个二进制来表明的不一样的算式只需纪录下她们的值,那样大家只要求max_i 和min_i出这种同样的二进制表明的算式max_i –min_i,最终大家就可以解出ans=max{max_i-min_i}。

根据位图文件,优化算法算法复杂度可将为O(N)。

3.2   检索

设计方案检索修枝时,必须储存早已检索过的历史时间信息内容,有一些状况下,能够应用位图文件减少历史时间信息内容数据信息所占室内空间。

3.3    缩小

(1)     在2.五亿个整数金额中找到不反复的整数金额,注,内存不够以容下这2.五亿个整数金额?

(2)     腾讯面试题:给40亿次不反复的unsigned int的整数金额,未排过序的,随后再给一个数,怎么才能分辨这一数是不是在哪40亿数量之中?

4. 小结

Bitmap是一种十分简约迅速的算法设计,他能同使证储存空间和速率最优控制(而无须室内空间换時间)。

5.  参考文献

(1)     《C实现bitmap位图》:

http://blog.csdn.net/QIBAOYUAN/archive/2010/09/29/5914662.aspx

(2)     武森《浅谈信息学竞赛中的“0”和“1”》

 

    关键字:

天才代写-代写联系方式