位图的详解

这篇具有很好参考价值的文章主要介绍了位图的详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

位图

位图的概念

位图的实现

位图常见三道面试题

1.给定100亿个整数,设计算法找到只出现一次的整数?

2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集? 

3. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数.


位图

位图的概念

先来看一下位图的概念

位图 (Bitmap) 是一种基于位操作的数据结构,用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组,其中每个元素对应集合中的一个元素。位图中的每个位(或者可以理解为数组的元素)代表一个元素是否存在于集合中。当元素存在时,对应位的值为1不存在时,对应位的值为0。位图常用于判断某个元素是否属于某个集合,或者对多个集合做交集、并集或差集等集合运算。

可能这么多听起来很复杂,其实总结下来就这个意思:

位图本质是个数组,用来存放0和1。

位图通过自身数组中的每个来代表集合(我们要处理的数据)中的元素,每个是0或1,代表元素的存在与否(0,不存在;1,存在)。

我们先看一下下面的例子:

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

1.首先当然可以遍历这40亿个数,这样效率会太低了,肯定直接pass掉.

2.也可以考虑搜索树或者哈希表,操作之前一定要把数据先存下来构建树或表。但是仔细一想,40亿个数,占多少空间?

40亿个无符号整数,每个大小4个字节,则一共占用160亿字节。

1GB = 1024 MB, 1MB  = 1024KB, 1KB = 1024Byte(字节).

所以一共占用16000000000/1024/1024/1024≈14.9G.

所以要用这些方法的话一上来就占用14.9G的系统内存,大多数电脑是吃不消的,更别说搜索树结点还存其他属性信息,现在内存16G的电脑也不算很多。这肯定不行的.

3.当然还可以存在磁盘上,进行外排序+二分查找。但是想一下,这一切是在磁盘上进行,磁盘的速度可是非常慢的,而且要对这么多数据排序,以及在磁盘上进行二分查找,无论代码还是时间都是复杂和比较慢的.

下一个方法,就是我们大名鼎鼎的位图来解决了,具体是怎么样的呢?

首先,我们要给数组开辟一块空间,这片空间我们开多少呢,要根据数据范围开空间,而不是数据个数。

这个我相信大家都能理解,毕竟如果只有两个数,一个是1,一个数是40亿,按数据个数开两个空间的话只能存下1和2,40亿肯定是存不下的。

所以无符号整型的数据范围是0~2^32-1,所以我们要开这么大的空间.那么一共多大呢?

由于我们是使用比特位进行表示每一个数是否存在的,所以相当于是2^32-1个比特位。由于1byte=8bit.根据上面所说,一共占用(2^32-1)/8/1024/1024/1024=0.5GB=512MB. 

所以我们开好空间以后,我们只需要将数对应的位置为1即可.

比如数据{1,4,9,15,17,23},在位图中是什么样的?

位图的详解,数据结构,c++,位图

 这样到时候直接判断对应位置是不是1即可判断某个数是否存在.

具体怎么设置,取消,判断看下面。

位图的实现

主要包含三个核心接口:设置(设为1)、重置(设为0)、判断(是0还是1)

对于每一步可以看注释.

#include<iostream>
#include<vector>
using namespace std;

namespace hyx
{
    //N代表数据范围
	template<size_t N>
	class bit_set
	{
	public:
		bit_set()
		{
			_bits.resize(N / 8 + 1, 0);
		}
		void set(size_t x)
		{
			//由于一个组是char,所以x/8是计算在哪个char组里
			size_t i = x / 8;
			//一个char里有8位,x%8是计算出在char组里面的具体哪一位
			size_t j = x % 8;
			//这个建议大家画图理解,首先_bits[i]是对应的char组,然后1<<j,其实是将1向左移动了j位,然后再或等,这样就把对应位置上的数置为1了,可以画图理解.
			_bits[i] |= (1 << j);
		}
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			//也是先1向左移动j位,然后再按位取反,此时除了目标位是0,别的位都是1.然后再&上这个数,任何数&1都是它本身,&0都是0.所以此时将目标位设置为0了
			_bits[i] &= ~(1 << j);
		}
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			//任何数&1都是它本身,因为我们可以利用这一点来判断目标位是0还是1.
			//注意此时不再需要加等于号了,因为这是判断,不是修改。
			return _bits[i] & (1 << j);
		}
	private:
		vector<char> _bits;
	};
}

 接下来你可以测试一些数据,比如set一些或reset一些.

当然如果想创建无符号整数的测试集,范围是0~2^32-1,可以直接用-1替代,因为-1的二进制是全1.

转化为无符号整数就是最大的。或者0xffffffff。同样地道理。如下

hyx::bit_set<-1> bs1;

这样创建即可.

位图常见三道面试题

下面来几个位图的拓展题:

1.给定100亿个整数,设计算法找到只出现一次的整数?

首先100亿个整数会不会有空间的问题?答案是肯定不会的,因为开空间和数据范围有关系,和数据个数没有关系,100亿个整数,每个数的范围都是42亿(2^32-1)之内,不会说有100亿个不重复的整数.

首先问题是找出现一次的整数,很明显是个key-value模型。那这至少需要两个位图了。所以就需要建立双位图解决.

既然求出现一次,那么肯定是以下三种情况:(左边次数,右边对应的位图状态)

0次                     00

1次                     01

2次及以上          10

所以上面可知,第二个位图是由两个位进行表示.这样又得需要各种控制,也是不太方便.

其实位图也是一个数据结构,STL库中也有对应的容器——bitset.

 那我们直接用两个位图分别表示这两个位不就可以了吗,当然!

所以我们要自己建立一个有两个位图的类,如下

整体思路是:依次判断两个位:

1.若为00,说明这个数一次也没出现过,将其改为01.即将第二个位图设为1.

2.若为01,说明这个数出现了一次,将其改为10,即第一个位图设为1,第二个位图设为0.

 后面可以写一个成员函数来输出符合条件的数:

template <size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		bool inset1 = _bs1.test(x);
		bool inset2 = _bs2.test(x);
		//00
		if (inset1 == false && inset2 == false)
		{
			//->01
			_bs2.set(x);
		}
		else if (inset1 == false && inset2 == true)
		{
			//->10
			_bs1.set(x);
			_bs2.reset(x);
		}
	}
		void print_once_num()
		{
			for (int i = 0; i < N; i++)
			{
				//筛选出两个位图为01的数
				if (_bs1[i] == false && _bs2[i] == true)
				{
					cout << i << endl;
				}
			}
		}
private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};
void test_oncenum()
{
	int a[] = { 1,1,2,3,4,5,5,5,6,6,6,6,7,9,22 };
	twobitset<100> bs;
	for (auto e : a)
	{
		bs.set(e);
	}
	bs.print_once_num();
}

 然后我们调用测试函数,得到:

位图的详解,数据结构,c++,位图

可以发现已经输出了出现个数只为1的数.

2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集? 

这道题比较简单,思路是建立两个位图,然后分别把两个文件里的数据set到位图里,然后最后将两个位图&一下,然后再从最后的结果中找位是1的即可(利用test).

3. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数.

这个题和1题类似,无非就是多了一种状态:3次及3次以上。最后对应的状态是以下这样:

0次                     00

1次                     01

2次                     10

3次及3次以上     11

然后要在twobitset的set中多加一个判断条件:当位图位10时,下一次改为11.

		//10
		else if (inset1 == true && inset2 == false)
		{
			//->11
			_bs2.set(x);
		}

然后输出的时候变化条件为bs1[i]==true和bs2[i]==true(11)即可.

至此,位图的所有内容就结束了,若有不懂或疑问的地方,欢迎私信或评论~文章来源地址https://www.toymoban.com/news/detail-520611.html

到了这里,关于位图的详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】盘点那些经典的 [哈希面试题]【哈希切割】【位图应用】【布隆过滤器】(10)

    前言 大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《

    2024年02月04日
    浏览(59)
  • 数据结构与算法——数据结构有哪些,常用数据结构详解

    数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构

    2024年02月15日
    浏览(63)
  • 【数据结构】详解链表结构

    上篇博客已经介绍了顺序表的实现:【数据结构】详解顺序表。最后在里面也谈及了顺序表结构的缺陷,即 效率低,空间浪费 等等问题,那么为了解决这些问题,于是乎我们引入了链表的概念,下面将对链表结构进行讲解 首先肯定会问,到底什么是链表? 链表的概念 : 链

    2024年02月05日
    浏览(44)
  • 【数据结构】C语言结构体详解

    目录 前言 一、结构体的定义 二、定义结构体变量 三、结构体变量的初始化 四、使用typedef声明新数据类型名 五、指向结构体变量的指针 总结 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CSDN📚。 📣如需转

    2024年02月04日
    浏览(49)
  • Redis内部数据结构Dict结构详解

    dict的数据结构定义 dict的创建(dictCreate) dict的查找(dictFind) dict的插入(dictAdd和dictReplace) dict的删除(dictDelete) 如果你使用过Redis,一定会像我一样对它的内部实现产生兴趣。《Redis内部数据结构详解》是我准备写的一个系列,也是我个人对于之前研究Redis的一个阶段性

    2024年01月21日
    浏览(39)
  • 数据结构之查找详解

    1.1 定义 查找表是由同一类型的数据元素构成的集合。 例如电话号码簿和字典都可以看作是一张查找表。 1.2 查找表的几种操作: 1)在查找表中查找某个具体的数据元素; 2)在查找表中插入数据元素; 3)从查找表中删除数据元素; 1.3 静态查找表和动态查找表 在查找表中

    2024年01月16日
    浏览(33)
  • 【数据结构】链表详解

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 在前面我们已经学习过了有关顺序表的知识,但是我们知道顺序表是存在着一些问题的 问题: 中间/头部的插入删除,时间复杂度

    2024年02月03日
    浏览(42)
  • [数据结构]——链表详解

    1.什么是链表?链表的概念及结构 链表是一种 物理存储结构上非连续、非顺序 的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的。 注意: 1.链式结构在逻辑上是连续的,但在物理上不一定连续 2.现实中的结点一般都是从堆上申请出来的 3.从堆上申请的

    2024年02月09日
    浏览(38)
  • 数据结构——链表详解

    new一个奶黄包:没关系,这条路我陪你走到底 单链表结构图 带头单循环链表结构图 双向循环链表结构图 带头双向循环链表结构图 链表特点 单链表在内存中,并不是连续存储的(逻辑上连续)。 不支持随机访问 插入时只需要改变指针指向 没有容量的概念 可以高效的在任意

    2024年02月12日
    浏览(37)
  • 【数据结构】链表 详解

    我们不废话,直入正题。 什么是链表? 来看看百度怎么说: 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包

    2023年04月19日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包