Целочисленные наборы являются одной из базовых реализаций ключей набора Redis. Когда набор содержит только целочисленные числовые элементы и количество элементов невелико, Redis использует набор целых чисел в качестве базовой реализации ключа набора.
Реализация 1 целого набора
Целочисленные наборы-это набор абстрактных структур данных, которые Redis использует для хранения целочисленных значений. Он может сохранять целочисленные значения int16_t, int32_t, int64_t и гарантировать, что в коллекции нет повторяющихся элементов.
каждый intset.h/int набор Структура представляет собой набор целых чисел:
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;- Кодировка: кодировка
- Длина: количество элементов, содержащихся в коллекции
- Содержимое []: Массив сохраненных элементов
Массивы содержимого являются базовой реализацией наборов целых чисел: каждый элемент набора целых чисел является элементом массива массива содержимого, каждый элемент в массиве упорядочен по размеру от малого до большого, и в массиве нет дубликатов.
Атрибут length записывает запись набора целых чисел Количество элементов , то есть длину массива содержимого.
Хотя структура интенсивности объявляет атрибут содержимого как массив типа int8_t, на самом деле массив содержимого не содержит никаких значений типа int8_t. Истинный тип массива содержимого зависит от значения атрибута кодирования. Например, если значение атрибута кодирования равно INT SET_ENC_INT16, то содержимое равно int. Для массива типа 16_t каждый элемент в массиве представляет собой целое значение типа int16_t, начиная от [-32768-32767] (2 ^ (16-1)).
Аналогично, значение кодировки равно INTSET_ENC_INT32, поэтому диапазон значений для каждого элемента в массиве равен: [-2147483648, 2147483647] (2 ^ (32-1).
Это также поднимает вопрос о том, что происходит, когда мы вставляем 129 в насекомое, кодировка которого INTSET_ENC_INT 8 (диапазон int8_t равен [-128, 127])?
Это также запускает обновление вставки. Соответственно, существуют и унижающие достоинство операции. Далее давайте подробно рассмотрим операции обновления и понижения intset.
2 Операция Обновления
Всякий раз, когда мы добавляем новый элемент в набор целых чисел, если тип нового элемента больше, чем тип кодировки набора целых чисел, сначала необходимо выполнить набор целых чисел. Обновление Затем новый элемент может быть добавлен в набор целых чисел.
Исходный код всей операции обновления выглядит следующим образом:
// 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 пересечение
Процесс вычисления пересечения можно грубо разделить на три части:
- Проверьте каждый набор и рассматривайте несуществующие наборы как пустые наборы. Как только появляется пустой набор, дальнейшие вычисления не требуются. Конечное пересечение – это пустое множество.
- Каждый набор сортируется по количеству элементов от меньшего до большего. Этот вид облегчает последующие вычисления, чтобы начать с наименьшего набора, с меньшим количеством обрабатываемых элементов.
- Первый набор (то есть наименьший набор) после сортировки пройден. Для каждого элемента первого набора выполняется поиск всех последующих наборов по очереди. В конечный набор результатов добавляются только элементы, найденные во всех коллекциях.
Следует отметить, что третий шаг выше-это поиск в коллекции. Для хранения набора int и dict временная сложность составляет O (log n) и O (1) соответственно. Однако, поскольку интенсивность используется только в небольших наборах, можно примерно считать, что поиск в наборе также имеет постоянную временную сложность.
4.2 Объединение
Операция объединения является самой простой, если все коллекции пройдены и каждый элемент добавлен в конечный результирующий набор. Добавление элементов в коллекцию автоматически удаляет дубликаты, поэтому нет необходимости обнаруживать наличие элементов при их вставке.
4.3 наборы различий
Существует два возможных алгоритма вычисления наборов разностей, и их временная сложность различна.
Первый алгоритм
Первый набор просматривается, и каждый его элемент по очереди ищется во всех последующих наборах. В конечный набор результатов добавляются только элементы, которые не найдены во всех коллекциях.
Временная сложность этого алгоритма равна O (N * M), где N-количество элементов в первом наборе, а M-количество наборов.
Второй алгоритм
- Добавьте все элементы первого набора в промежуточный набор.
- Просмотрите все последующие коллекции и удалите их из среднего набора для каждого элемента, с которым вы сталкиваетесь.
- Наконец, остальные элементы промежуточного набора составляют набор различий.
- Временная сложность этого алгоритма равна O (N), где N-сумма элементов всех множеств.
В начальной части вычисления набора разностей ожидаемая временная сложность двух алгоритмов будет оценена отдельно, а затем для выполнения вычисления будет выбран алгоритм с низкой сложностью. Необходимо отметить еще два момента:
- В какой-то степени первый алгоритм предпочтительнее, потому что он включает меньше операций и только добавляет, в то время как второй алгоритм сначала нужно добавить, а затем удалить.
- Если выбран первый алгоритм, то перед выполнением алгоритма все наборы после второго набора сортируются в соответствии с количеством элементов в реализации Redis. Этот вид облегчает поиск элементов с большей вероятностью, что позволяет быстрее завершить поиск.
5 Резюме
- Целочисленные наборы являются одной из базовых реализаций ключей набора.
- Целочисленные наборы хранят элементы коллекции упорядоченным и неповторяющимся образом. При необходимости тип базового массива изменяется в соответствии с типом вновь добавленного элемента.
- Операция обновления повышает гибкость работы и максимально экономит память.
- Коллекции могут продолжаться Пересечение, слияние и различие Операция набора.