[TOC]
整数集合是 Redis 集合键的底层实现之一. 当一个集合只包含整数值元素, 并且元素数量不多时, Redis 就会使用整数集合作为集合键的底层实现.
1 整数集合的实现
整数集合是 Redis 用于保存整数值的集合抽象数据结构. 它可以保存类型为 int16_t,int32_t,int64_t 的整数值, 并且保证集合中不会出现重复元素.
每个 intset.h/intset 结构表示一个整数集合:
- typedef struct intset {
- uint32_t encoding;
- uint32_t length;
- int8_t contents[];
- } intset;
encding: 编码方式
length: 集合包含的元素数量
contents[]: 保存元素的数组
contents 数组是整数集合的底层实现: 整数集合的每个元素都是 contents 数组的一个数组项, 各个项在数组中按值的大小从小到大有序排列, 并且数组中不包含重复项.
length 属性记录了整数集合记录的元素数量, 也就是 contents 数组的长度.
虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组, 但实际上 contents 数组并不保存任何 int8_t 类型的值, contents 数组的真正类型取决于 encoding 属性的值, 比如: 如果 encoding 属性的值为 INTSET_ENC_INT16, 那么 contents 就是一个 int16_t 类型的数组, 数组里的每个项都是一个 int16_t 类型的整数值, 取值范围为:[-32768-32767](2^(16-1)).
与之类似, encoding 的值为 INTSET_ENC_INT32, 那么数组每项的取值范围为:[-2147483648, 2147483647](2^(32-1).
这里也引发了一个问题, 当我们对一个 encoding 为 INTSET_ENC_INT8 的 intset, 插入 129 时(int8_t 的取值范围是 [-128, 127]), 会出现什么?
这也就引发了 intset 的升级操作. 与之对应, 也有降级操作. 接下来, 我们来详细认识下 intset 的升降级操作.
2 升级操作
每当我们要将一个新元素添加到整数集合时, 如果新元素的类型比整数集合的 encoding 类型大, 整数集合就需要先进行升级操作(upgrade), 然后才能将新元素添加到整数集合中.
整个升级操作源码如下:
- // intset.c/intsetUpgradeAndAdd()
- /* Upgrades the intset to a larger encoding and inserts the given integer. */
- static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
- uint8_t curenc = intrev32ifbe(is->encoding);
- uint8_t newenc = _intsetValueEncoding(value);
- int length = intrev32ifbe(is->length);
- int prepend = value <0 ? 1 : 0;
- /* First set new encoding and resize */
- is->encoding = intrev32ifbe(newenc);
- is = intsetResize(is,intrev32ifbe(is->length)+1);
- /* Upgrade back-to-front so we don't overwrite values.
- * Note that the "prepend" variable is used to make sure we have an empty
- * space at either the beginning or the end of the intset. */
- while(length--)
- _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
- /* Set the value at the beginning or the end. */
- if (prepend)
- _intsetSet(is,0,value);
- else
- _intsetSet(is,intrev32ifbe(is->length),value);
- is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
- return is;
- }
升级整数集合并添加新元素, 共分为三步进行:
扩展底层数组大小. 根据新元素的类型, 扩展整数集合底层数组的大小, 并为新元素分配空间.
元素转换, 并保持原有顺序. 将底层数组现有的所有元素, 都转换成与新元素相同的类型, 并将转换后的元素放在正确的位置上, 保证原有顺序不发生改变.
将新元素添加到底层数组中.
此外, 一旦因插入新元素引发升级操作, 就说明新插入的元素比集合中现有的所有元素的长度大, 所以这个新元素的值要么大于所有现有元素(正值), 要么就小于所有现有元素(负值), 那么:
在新元素小于所有现有元素时, 新元素就会被放在底层数组的最开头的位置, 即索引为 0 的位置;
在新元素大于所有现有元素时, 新元素就会被放在底层数组的最末尾的位置;
3 升级优势
整数集合的升级策略主要有以下两个好处:
提示整数集合的灵活性;
尽可能的节约内存;
3.1 提示灵活性
因为 C 语言是静态类型语言, 为了避免类型错误, 我们通常不会将两种不同类型的值放在同一个数据结构中.
但是, 因为有了升级操作, 整数集合可以通过它来自适应新元素, 所以我们可以随意地将 int16_t,int32_t, 和 int64_t 类型的整数添加到集合中, 而不必担心出现类型错误, 大大的提升了整数集合的灵活性.
3.2 节约内存
当然, 要让一个数组可以同时保存 int16_t,int32_t, 和 int64_t 类型的整数值, 我们可以粗暴的直接使用 int64_t 类型的数组作为整数集合的底层实现, 来保存不同类型的值. 但是, 这样一来, 即使添加到集合中的都是 int16_t,int32_t 类型的值, 数组也都是需要使用 int64_t 类型的空间去保存, 出现浪费内存的情况.
而整数集合的升级操作, 既能同时保存三种不同类型的值, 又可以确保升级操作只会在有需要的时候进行, 达到节省内存的目的.
4 交, 并, 差集算法
Redis 中的集合实现了交, 并, 差等操作, 相关操作可参加 t_set.c, 其中 sinterGenericCommand() 实现交集, sunionDiffGenericCommand() 实现并集和差集.
它们都能同时对多个集合进行元素. 当对多个集合进行差集运算时, 会先计算出第一个和第二个集合的差值, 然后再与第三个集合做差集, 依次类推.
接下来, 我们一起来认识下三个操作的实现思路.
4.1 交集
计算交集的过程大概可以分为三部分:
检查各个集合, 对于不存在的集合当做空集来处理. 一旦出现空集, 则不用继续计算了, 最终的交集就是空集.
对各个集合按照元素个数由少到多进行排序. 这个排序有利于后面计算的时候从最小的集合开始, 需要处理的元素个数较少.
对排序后第一个集合 (也就是最小集合) 进行遍历, 对于它的每一个元素, 依次在后面的所有集合中进行查找. 只有在所有集合中都能找到的元素, 才加入到最后的结果集合中.
需要注意的是, 上述第 3 步在集合中进行查找, 对于 intset 和 dict 的存储来说时间复杂度分别是 O(log n) 和 O(1). 但由于只有小集合才使用 intset, 所以可以粗略地认为 intset 的查找也是常数时间复杂度的.
4.2 并集
并集操作最简单, 只要遍历所有集合, 将每一个元素都添加到最后的结果集中即可. 向集合中添加元素会自动去重, 所以插入的时候无需检测元素是否已存在.
4.3 差集
计算差集有两种可能的算法, 它们的时间复杂度有所区别.
第一种算法
对第一个集合进行遍历, 对于它的每一个元素, 依次在后面的所有集合中进行查找. 只有在所有集合中都找不到的元素, 才加入到最后的结果集合中.
这种算法的时间复杂度为 O(N*M), 其中 N 是第一个集合的元素个数, M 是集合数目.
第二种算法
将第一个集合的所有元素都加入到一个中间集合中.
遍历后面所有的集合, 对于碰到的每一个元素, 从中间集合中删掉它.
最后中间集合剩下的元素就构成了差集.
这种算法的时间复杂度为 O(N), 其中 N 是所有集合的元素个数总和.
在计算差集的开始部分, 会先分别估算一下两种算法预期的时间复杂度, 然后选择复杂度低的算法来进行运算. 还有两点需要注意:
在一定程度上优先选择第一种算法, 因为它涉及到的操作比较少, 只用添加, 而第二种算法要先添加再删除.
如果选择了第一种算法, 那么在执行该算法之前, Redis 的实现中对于第二个集合之后的所有集合, 按照元素个数由多到少进行了排序. 这个排序有利于以更大的概率查找到元素, 从而更快地结束查找.
5 总结
整数集合是集合键的底层实现之一.
整数集合以有序, 无重复的方式保存集合元素. 在有需要时, 会根据新添加元素的类型, 改变底层数组的类型.
升级操作提升了操作的灵活性, 并尽可能的节约了内存.
集合可以进行交, 并, 差集操作.
来源: https://www.cnblogs.com/BeiGuo-FengGuang/p/11337870.html