정수 집합(intset)은 집합 키의 기본 구현 중 하나입니다. 집합에 정수 값 요소만 포함되어 있고 이 집합의 요소 수가 크지 않은 경우 Redis는 정수 집합을 집합 키의 기본 구현으로 사용합니다. .
127.0.0.1:6379> sadd numbers 1 2 3 4 5 (integer) 5 127.0.0.1:6379> object encoding numbers "intset"
이것의 장점은 집합에 소수의 정수 요소만 있을 때 sds와 같이 이전에 소개된 다른 데이터 구조를 사용하면 상대적으로 많은 양의 메모리를 차지하게 되지만, 다음과 같은 경우에는 더 경제적입니다. 이는 정수 세트로만 저장됩니다.
정수 배열의 정의는 다음과 같이 intset.h에 있습니다.
typedef struct intset {
uint32_t encoding; // 编码方式
uint32_t length; // 保存的元素个数
int8_t contents[]; // 保存元素的数组
}
intset;intset 구조는 내용 속성을 int8_t 유형의 배열로 선언하지만 실제로 내용 배열은 내용을 저장하지 않습니다. int8_t 유형의 값 ——컨텐츠 배열의 실제 유형은 인코딩 속성의 값에 따라 다릅니다.
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) {
if (v < INT32_MIN || v > INT32_MAX)
return INTSET_ENC_INT64;
else if (v < INT16_MIN || v > INT16_MAX)
return INTSET_ENC_INT32;
else
return INTSET_ENC_INT16;
}int_16, int_32, int_64에 해당하는 총 세 가지 유형이 있음을 알 수 있습니다.
정수 배열의 모든 요소는 작은 것부터 큰 것 순으로 배열되어 있으며, 배열에는 중복된 내용이 없습니다.
// 初始化空的整数集合intset *intsetNew(void) {
intset *is = zmalloc(sizeof(intset));
is->encoding = intrev32ifbe(INTSET_ENC_INT16); // 默认创建int_16的编码格式
is->length = 0;
return is;
}/* Insert an integer in the intset */intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
uint8_t valenc = _intsetValueEncoding(value);
uint32_t pos;
if (success) *success = 1; // 如果超出了当前编码格式所能表示的范围，则升级整数集合并添加元素
if (valenc > intrev32ifbe(is->encoding)) {
/* This always succeeds, so we don't need to curry *success. */
return intsetUpgradeAndAdd(is,value);
} else { // 如果元素已经存在于集合，success返回0
// 如果不存在的话， 这个函数会返回元素应该插入的位置pos
if (intsetSearch(is,value,&pos)) {
if (success) *success = 0;
return is;
} // 否则，需要重新调整集合的大小
is = intsetResize(is,intrev32ifbe(is->length)+1); // 将pos之后的数据全都向后挪动一个位子
if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
}
_intsetSet(is,pos,value); // 添加数据到第pos位
is->length = intrev32ifbe(intrev32ifbe(is->length)+1); // 调整元素个数
return is;
}요소를 삽입할 때 사용되는 인코딩은 새 요소의 크기에 따라 다시 결정되어야 합니다. 새 요소가 원래 인코딩의 표현 범위를 초과하는 경우 인코딩을 조정해야 하며 컬렉션에 있는 다른 모든 요소의 인코딩 형식을 조정해야 합니다. 인코딩 조정은 되돌릴 수 없는 프로세스입니다. 즉, 작은 인코딩에서 큰 인코딩으로만 조정할 수 있으며 업그레이드만 가능하고 다운그레이드는 불가능합니다.
정수 세트를 업그레이드하고 새 요소를 추가하면 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);
// 由于整数集合是一个有序集合，所以新的这个超出范围的元素，要不插入头部，要不插入尾部
// 当value大于0的时候，就是插入到尾部，否则插入到头部，用参数prepend来标记
int prepend = value < 0 ? 1 : 0;
/* First set new encoding and resize */
// 重新设置整数集合的编码
is->encoding = intrev32ifbe(newenc); // 根据新编码调整整数集合的大小
is = intsetResize(is,intrev32ifbe(is->length)+1); // 从尾部向头部进行升级，这样在挪动其中的元素的时候，不会覆盖原来的值
while(length--)
// 如果新元素是插入到尾部，prepend==0， 所以原来最后的元素是挪动到length位置
// 如果新元素是插入到头部，prepend==1，所有的元素都要向后挪动一个位置，将头部空出来
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/* Set the value at the beginning or the end. */
if (prepend)
// 如果prepend==1， 插入到头部
_intsetSet(is,0,value);
else
// 否则，设置最后一个位置的元素为value
_intsetSet(is,intrev32ifbe(is->length),value); // 元素个数加1
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}정수 컬렉션에 대한 현재 접근 방식은 컬렉션이 동시에 세 가지 유형의 값을 저장할 수 있을 뿐만 아니라 필요한 경우에만 업그레이드 작업이 수행되도록 보장하여 메모리를 최대한 절약할 수 있습니다. 가능한 한.
검색할 때 먼저 찾고 있는 요소가 현재 인코딩의 유효한 범위 내에 있는지 확인해야 합니다. 현재 범위 내에 있지 않으면 직접 반환할 수 있습니다.
그리고 정수집합은 순서집합이기 때문에 이진탐색도 가능합니다,
uint8_t intsetFind(intset *is, int64_t value) { // 获得目标值的编码
uint8_t valenc = _intsetValueEncoding(value); // 只有目标值的编码比当前编码小，才继续执行查找过程
return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}// 如果找到这个元素，返回1，同时pos表示这个值在整数集合里边的位置
// 如果没有找到这个元素，返回0， 同时pos表示这个值可以插入的位置
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
/* The value can never be found when the set is empty */
// 如果集合的长度为0， 直接返回0
if (intrev32ifbe(is->length) == 0) {
if (pos) *pos = 0;
return 0;
} else {
/* Check for the case where we know we cannot find the value,
* but do know the insert position. */
// 如果目标值大于当前最大值，肯定找不到，返回0， 同时待插入的位置pos为length
if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
if (pos) *pos = intrev32ifbe(is->length);
return 0;
} else if (value < _intsetGet(is,0)) {
// 如果目标址小于当前最小值，返回0， 同时待插入的位置pos为0
if (pos) *pos = 0;
return 0;
}
} // 二分查找
while(max >= min) { // 得到中间位置
mid = ((unsigned int)min + (unsigned int)max) >> 1; // 得到中间位置的值
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
} if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}위 내용은 Redis의 작은 정수 컬렉션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
