当前位置: 首页 > news >正文

无锡专业网站制作百度风云搜索榜

无锡专业网站制作,百度风云搜索榜,极速时时彩网站建设,分分彩做号网站1. 位图的概念 位图(Bitmap)是一种基于位操作的数据结构,用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组,每个元素对应一个二进制位,若该元素存在,则对应的位为1;若不存在&#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
{template<size_t N>class 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:vector<int> _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位,以此类推。

template<size_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:bitset<N> _bs1;bitset<N> _bs2;
};

先简单介绍一下,之后可能更新。

http://www.ds6.com.cn/news/61385.html

相关文章:

  • b站广告投放全网推广推荐
  • 网红营销策略分析快速整站优化
  • wordpress微信说说影响关键词优化的因素
  • 做网站前端难吗百度 营销中心
  • 网站建设市场行情报价新的营销模式有哪些
  • 2017网站建设价目表seo网络推广培训
  • 站长工具在线免费观看2019年 2022疫情爆发
  • 怎么做网站运营编辑的简历真正免费的建站
  • 怎么搭建源码网站西安seo优化顾问
  • 微网站第三方平台广州推动优化防控措施落地
  • 扬中网站建设seo是什么意思网络用语
  • 网站 java php饥饿营销的十大案例
  • php与java做网站网站搭建模板
  • 美橙域名查询网站seo关键词排名优化是什么
  • 好用的种子搜索引擎惠州seo关键字优化
  • 外接硬盘做创建立网站百度关键词排名十大排名
  • 海力建设集团有限公司网站长春最新发布信息
  • 网站换ip影响 百度游戏推广渠道
  • vs网站搜索栏怎么做北京口碑最好的it培训机构
  • 网站建设 课程 说明市场营销培训
  • 中国排名高的购物网站微信营销推广
  • wordpress 排课武汉seo论坛
  • 成都模板网站建设惠州seo关键字优化
  • 做文学网站用什么域名品牌推广的方式有哪些
  • 惠州抖音推广怎么寻找网站关键词并优化
  • 牙医工具网站建设课程设计报告写一篇软文推广自己的学校
  • 网站开发与维护学什么百度搜索引擎原理
  • 有没有可以做司考真题的网站外贸google推广
  • 营销型网站建设公司比较专业故事式软文范例500字
  • 广州微信网站建设费用百度客服人工