数据结构之位图(bitmap)详解
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.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数?
(2)腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
4. 总结
Bitmap是一种非常简洁快速的数据结构,他能同使证存储空间和速度最优化(而不必空间换时间)。
5. 参考资料
(1)《C实现bitmap位图》://www.jb51.net/article/54438.htm
(2)武森《浅谈信息学竞赛中的“0”和“1”》
相关文章
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了c# 如何实现位图算法(BitMap),文中讲解非常细致,帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-11-03
- 本文主要和大家分享几种Redis数据结构详解,希望文中的案例和代码,能帮助到大家。...2021-01-15
- 这篇文章主要为大家详细的介绍了Redis高效的原因以及分析了Redis高效的数据结构,有需要的朋友可以借鉴参考下,希望能够有所帮助...2021-09-27
- 上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构——线性结构...2020-06-25
- 这篇文章主要介绍了C语言数据结构递归之斐波那契数列的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++数据结构与算法之哈夫曼树的实现方法,简单说明了哈夫曼树的原理,并结合具体实例形式分析了C++实现哈夫曼树的相关操作技巧,需要的朋友可以参考下...2020-04-25
- 很多应用上都有用户签到的功能,尤其是配合积分系统一起使用。本文主要介绍了Redis基于Bitmap实现用户签到功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-06-18
- 这篇文章主要介绍了基于JavaScript的数据结构队列动画实现示例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-06
- 这篇文章主要介绍了C++将CBitmap类中的图像保存到文件的方法,涉及C++导出资源文件的实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了数据结构 双向链表的创建和读取详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之动态分配实现串的相关资料,希望通过本文能帮助到大家,让大家实现数据结构中动态分配实现串的实例,需要的朋友可以参考下...2020-04-25
- <? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){...2016-11-25
- 我们在进行编程时,往往会开发诸多的算法,那么我们怎么在那么多算法中找到最好的那个呢?本文主要介绍时间和空间复杂度概念及时间复杂度的求解,预祝读者学习愉快...2021-10-23
- 这篇文章主要介绍了C++数据结构与算法之双缓存队列实现方法,结合实例形式分析了双缓存队列的原理、实现方法与相关注意事项,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构树的双亲表示法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中数据结构之链式基数排序的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之使用链表模拟栈的实例的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了数据结构之树的概念详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-09-10