软件外包行业分析,湖南正规竞价优化公司,5g创业网站建设,江门网站建设方案推广1. 位图的概念 位图#xff08;Bitmap#xff09;是一种基于位操作的数据结构#xff0c;用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组#xff0c;每个元素对应一个二进制位#xff0c;若该元素存在#xff0c;则对应的位为1#xff1b;若不存在#xff…1. 位图的概念 位图Bitmap是一种基于位操作的数据结构用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组每个元素对应一个二进制位若该元素存在则对应的位为1若不存在则为0。位图的这种表示方式使得它能够在存储上以极高的空间效率来管理大规模数据。位图特别适用于需要频繁查询和更新的场景如数据库索引、图像处理和网络协议等。 简单来说就是一个采用直接定址法的哈希表只不过一个bit位映射一个数。
底层通常是一个存储整形的数组或vector将其中的整形数据连起来看作一个存储bit位的数组。下标为n的bit位为1代表n存在为0代表n不存在。 这样一来位图存储一个数据的消耗仅为一个bit位相比于红黑树和哈希表在对大量的整形数据的进行增删查改时位图的优势就十分明显了。 优点增删查改效率极高空间复杂度低。 缺点只适用于整型。 2. 位图的实现
STL的 bitset 就是位图其有三个主要接口set(插入)reset(删除)test(查找)。
bitset - C Reference
位图的实现比较简单就不过多介绍了。
namespace lbz
{templatesize_t Nclass bitset{public:bitset():_bs(N / 32 1, 0){}void set(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] | (1 j);}void reset(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] ~(1 j);}bool test(size_t x){size_t i x / 32;size_t j x % 32;return _bs[i] (1 j);}private:vectorint _bs;}; 注意这里无需在意大小端的问题因为bit 位的下标只是假想的下标。
我们只需要算出代表x的bit位是哪一个整形中的第几个并保证各个接口采用相同的逻辑查找即可。
3. 位图的应用
3.1 检查数据是否存在
eg给40亿个不重复的无符号整数没排过序。如何判断某个无符号数是否在这40亿个数中腾讯、百度等公司出过的面试题。 思路1暴力遍历---时间复杂度O(N)太慢 思路2排序二分查找---时间复杂度O(N * logN) O(logN)排序消耗大但是排好序之后可以进行多次查找。 但是上面两种思路都存在着一个问题那就是需要将40亿个整数存到内存中。
40亿个整数约等于16GB考虑到电脑中的其他进程开出这么大的一个数组显然是不现实的。
这时候就可以使用位图来解决位图中开辟 UINT_MAX 个字节(数据范围为0~UINT_MAX)并将数据存储到位图中。此时数据对内存的占用就可以降低到500MB左右且查找效率为O(1)。
3.2 计算数据个数
eg给100亿个不重复的无符号整数没排过序。如何找出出现次数小于2的数据
一个bit位只能判断存不存在如果要计数就只能用多个比特位来映射一个数。
这里我们可以采用包装多个位图的方式来实现第一个位图存储第一个bit位第二个位图存储第二个bit位以此类推。
templatesize_t N
class two_bitset
{
public:void set(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2)// 00 1{_bs2.set(x);}else if (!bit1 bit2)// 01 1{_bs1.set(x);_bs2.reset(x);}else if (bit1 !bit2)// 10 1{_bs2.set(x);}}void reset(size_t x){_bs1.reset(x);_bs2.reset(x);}int test(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2)// 00{return 0;}else if (!bit1 bit2)// 01{return 1;}else if (bit1 !bit2)// 10{return 2;}else{return 3;}}
private:bitsetN _bs1;bitsetN _bs2;
};
先简单介绍一下之后可能更新。
