皮皮网

【怎么查找网页视频源码编辑】【押注源码】【志成源码】bitset的源码_bitset原理

2024-12-25 14:49:48 来源:湖北区块链开发源码交付

1.BitMap原理与实现
2.位向量工作原理
3.size_t的介绍
4.一文看懂ECS架构

bitset的源码_bitset原理

BitMap原理与实现

        比较经典的问题是: 在只能够使用2G的内存中,如何完成以下操作:

        ①:对亿个不重复的整数进行排序。

        ②:找出亿个数字中重复的数字。

        无论是排序还是找重复的数字都需要将这亿个数字加入到内存中在去进行操作,很明显,题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

        * 4/(* * ) = 3.G

        那么这时候就需要用到 BitMap结构了

        bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,而map的key值正是这个数字本身。

        相比于一般的数据结构需要用4个byte去存储数值本身,相当于是节省了 4*8:1 = 倍的内存空间

        bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现,因为其实质都是在bit位上存数据,用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

            例如:java中的BitSet使用Long数组

        BitMap的实现当然少不了位运算,先来明确几个常见位运算,这是实现BitMap的基础:

        set(bitIndex): 添加操作

            1 .确定该数处于数组中的哪个元素的位上

             int wordIndex = bitIndex >> 5;

        因为我用的是int[]实现,所以这里右移 5 位(2^5 = )

            2 .确定相对于该元素中的位置偏移

             int bitPosition = bitIndex & ((1 << 5) - 1);

        这里相当于是 bitIndex % (1<<5)的取模运算,因为当取模运算的除数是2的次幂,所以可以使用以下的位运算来计算,提升效率(对比HashMap的容量为什么总是2的幂次方的问题,HashMap求下标时也是使用 hash&(n-1))

        tips: 位运算的优先级是低于+,-等等的,所以要加上括号,防止发生不可描述的错误

            3 .将该位置1

             bits[wordIndex] |= 1 << bitPosition;

        相当于是将指定位置处的bit值置1,其他位置保持不变,也就是将以这个bitIndex为key的位置为1

        tips: 这里是参考了网上的各位大佬的文章,取余 + 按位或,又对比了下BitSet的源码:

             words[wordIndex] |= (1L << bitIndex);

        没有取余操作,直接|,这两个一样吗?答案当然是一样的

        举个栗子:

             1 << == 1<<     

             1L << ==1L<<

        即对于int和long型数据,直接左移其位数相当于是附带了对其的取模操作

        总结:使用Bit-map的思想,我们可以将存储空间进行压缩,而且可以对数字进行快速排序、去重和查询的操作。

        Bloom Fliter是Bit-map思想的一种扩展,它可以在允许低错误率的场景下,大大地进行空间压缩,是一种拿错误率换取空间的数据结构

        当一个元素加入布隆过滤器中的时候,会进行哪些操作:

        当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行哪些操作:

        然后,一定会出现这样一种情况:不同的字符串可能哈希出来的位置相同(可以适当增加位数组大小或者调整我们的哈希函数来降低概率),因此:布隆过滤器可能会存在误判的情况

        总结来说就是: 布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在。

        Bloom Filter的应用: 常用于解决缓存穿透等场景。

位向量工作原理

       位向量,也叫位图,是一个我们经常可以用到的数据结构,在使用小空间来处理大量数据方面有着得天独厚的优势;位向量的定义就是一串由0.1组成的序列。

       Java中对位向量的实现类时Java.util.BitSet;C++标准库中也有相应的实现,原理都是怎么查找网页视频源码编辑一样的; BitSet源码也很简单,很容易看懂 ,如果读者在对位向量有一定的了解后,可以通过读源码来了解BitSet的具体实现。

       一个bit上有两个值,正好可以用来判断某些是非状态的场景,在针对大数据场景下判断存在性,BitSet是相比其他数据结构比如HashMap更好的选择,在Java中,位向量是用一个叫words的long型数组实现的,一个long型变量有位,可以保存个数字;比如我们有[2,押注源码8,6,,]这5个数要保存,一般存储需要 5*4 = 字节的存储空间。但是如果我们使用Java.util.BitSet进行存储则可以节省很多的空间只需要一个long型数字就够了。BitSet只面向数字只面向数字使用,对于string类型的数据,可以通过hashcode值来使用BitSet。

       由于,1 << , 1<<, 1<< 这些数字的结果都为1,BitSet内部,志成源码long[]数组的大小由BitSet接收的最大数字决定,这个数组将数字分段表示[0,],[,],[,]...。即long[0]用来存储[0,]这个范围的数字的“存在性”,long用来存储[,],依次轮推,这样就避免了位运算导致的冲突。原理如下:

       |------------|----------|----------|----------|----------| |

       Java的BitSet每次申请空间,申请位,peis 源码即一个long型变量所占的位数;

size_t的介绍

       size_t 类型定义在cstddef头文件中,该文件是C标准库的头文件stddef.h的C++版。它是一个与机器相关的unsigned类型,其大小足以保证存储内存中对象的大小。例如:bitset的size操作返回bitset对象中二进制位中的个数,返回值类型是size_t。例如:在用下标访问元素时,vector使用vector::size_type作为下标类型,而数组下标的正确类型则是size_t。vector使用的下标实际也是size_t,源码是typedef size_t size_type。

一文看懂ECS架构

       在游戏开发中,ECS架构是一种解决实际问题的高效方式。其核心思想是通过组合和数据打包优化性能,而非传统的继承结构。以下是ECS架构的三个关键部分的概述。

       实体(Entity):每个实体仅包含一个唯一的ID,代表其身份。

       组件(Component):组件是mstar源码相关功能数据的集合,如Transform组件包含位置和旋转信息。每个组件类型对应一个独一无二的ID,用于跟踪和匹配。

       签名(Signature):通过std::bitset表示实体拥有的组件集合,每个组件类型在位图中对应一个位置。系统通过比较其关心的组件签名和实体签名,确保所需组件的匹配。

       实体管理器(EntityManager):负责ID的分配与回收,使用队列管理可用ID,保证高效创建和销毁操作。

       组件数组(Component Array):存储同类型组件的数据,通过映射保持数据紧凑,避免无效数据影响性能。当实体被销毁,数据需重新组织以保持数组连续性。

       系统(System):关注特定组件签名的实体列表,通过std::set保持高效查找,处理相关组件的逻辑。

       系统管理器(System Manager):维护已注册系统及其签名,确保与Component Manager和EntityManager的协调。

       协调器(Coordinator):整合所有Manager,提供跨Manager操作的接口,简化代码结构。

       通过一个实例,比如,立方体受重力影响的场景,ECS架构展示出其在性能上的优势。但也要注意,ECS不适用于所有场景,通常在对性能要求高的部分,如物理模拟,采用ECS。

       学习ECS架构的深入资料可以参考Austin Morlan的"A Simple Entity Component System (ECS) [C++]",源代码和详细解释可在相关链接中获取。