Расширенные связанные списки: основное руководство

Как работает связанный список?

Связанный список — это структура данных, в которой поля каждых данных соединены указателями, а не смещениями. Он состоит из главного элемента, в котором хранятся первый и последний элементы, так называемые элементы узла, содержащие все необходимые пользовательские поля (например, телефон, владелец, компания и т. д.) и указатель на следующий узел. Последний элемент связан с полем NULL, которое указывает на конец списка.

Когда в связанный список добавляется новый элемент, главный узел должен обновить указатель «хвоста» на новый конечный узел, а предыдущий NULL-указатель должен быть обновлен до нового хвоста.

Эта структура данных позволяет эффективно записывать новые данные без изменения размера всего массива. Это эффективный метод хранения данных, доступных только для записи, и он не требует предварительного знания количества элементов. Это простая структура данных, и в памяти она выглядит так:

Связанный список для ключей выселения

В более ранней статье мы обсуждали необходимость наличия буфера для сканирования дерева без выхода из дерева после каждого удаления элемента. В языках с GC это не проблема. Однако, когда код приложения управляет памятью, решением может стать буфер на основе связанного списка, содержащего устаревшие элементы.

Связанный список позволяет быстро добавлять элементы. Однако поиск чего-либо в связанном списке требует последовательного сканирования, что делает его непригодным для быстрого извлечения ключей. Таким образом, это эффективное решение для регистрации данных, создания временных буферов и организации данных для последовательного чтения с головных узлов.

Поиск элементов для вытеснения является примером такой задачи. Вытеснение часто используется в различных реализациях кэша. Кэш содержит данные, которые можно восстановить из других источников памяти с большей задержкой. Кэш обычно хранится в основной памяти. Основная память ограничена, и для эффективного использования в основной памяти можно хранить только небольшой снимок данных.

Это требует от нас более разумного использования памяти, избегания использования памяти для редко запрашиваемых данных и удаления таких данных, если они запрашиваются слишком редко.

Эффективным методом удаления полей из кэша является метод «Наименее недавно использовавшийся» (LRU). Вот представление LRU ниже:

В этом случае приложение включает в себя как минимум один связанный список для хранения недавно использованных объектов и другие структуры данных (например, хеш-таблицу) для быстрого поиска. Узлы связаны между собой.

Когда пользователь извлекает данные из хеш-таблицы, связанный список обновляет эти данные, перемещая их в хвост. В результате после нескольких операций хвост содержит недавно использованные данные, а голова — редко запрашиваемые данные.

В случае переполнения памяти приложение может сканировать первые N элементов, чтобы освободить достаточно памяти. Это простая операция, поскольку связанный список адаптируется к последовательному сканированию. Память с редко используемыми данными будет освобождена, а новые более частые узлы можно будет хранить в кеше.

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

Одно замечание: когда количество используемых элементов существенно различается по частоте (например, 95% запросов распределяются по верхним 100 ключам из 1 миллиона), Splay Tree может оказаться более подходящим для хранения кеша. Это дерево сбалансировано на основе частоты использования каждого узла.

Основная идея Splay Tree противоположна LRU — наиболее используемые элементы расположены вблизи корня, что делает эту структуру данных идеальной в качестве первичной структуры для кэша.

Вытеснение можно решить двумя способами: с помощью связанного списка, связанного с основной структурой, или путем изменения дерева расширения на поточное двоичное дерево. Узлы в дереве расширения уже отсортированы по частоте использования. Хотя дополнительная резьба листьев деревьев может потребовать больше процессорного времени, следовательно, она может сэкономить память.

Чтобы лучше понять ускорение недавно использованных данных в памяти, вы можете изучить пример живой миграции ВМ по этой ссылке .

Улучшите скорость сканирования связанного списка

Как упоминалось ранее, связанные списки предлагают самое быстрое решение для записи данных. Скорость сканирования у них хорошая, но она медленнее скорости сканирования в массиве.

Эту проблему как локальность данных я описал в предыдущей статье . Однако, поскольку связанные списки похожи на двоичные деревья, их можно улучшить. Развертывание связанных списков позволяет хранить больше данных в каждом узле списка. Таким образом, он экономит память на следующем узле указателя, а иногда и повышает производительность при условии, что размер элемента соответствует строке кэша ЦП:

Основная идея останется неизменной, но представление списка в памяти изменится.

Оно изменится во многих отношениях. Ниже есть 2 варианта:

Эти улучшения повышают производительность связанных списков, но усложняют код. Для дисковых операций со связанным списком развернутый узел может иметь больше элементов. Самый простой способ понять, как это работает, — представить связанный список массивов.

В коде нам нужно изменить описание структуры и с этого момента читать или записывать каждый элемент массива структуры:

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

Пропустить список

Список пропуска — это метод улучшения скоростных характеристик элементов поиска в связанном списке. Этот тип связанного списка хранит ключ для упорядочивания связанного списка и включает дополнительные указатели для более эффективного поиска узлов, чем простая операция сканирования.

Дополнительные узлы повышают скорость перемещения между узлами в списке пропуска. Это работает как двоичный поиск. Напротив, на добавление новых элементов уходит больше времени. Поэтому списки пропусков должны иметь ключ. Приложения могут делать любое количество уровней для улучшения скоростных характеристик. В большинстве случаев лучшим выбором будет иметь немного меньшие или примерно такие же уровни, что и высота дерева. (Смотрите картинку выше)

При поиске приложение начинается с самого высокого уровня, который является самым быстрым маршрутом. При обнаружении ближайшего ключа он опускается на более низкий уровень, пока не будет найден нужный узел.

Этот процесс приводит к временной сложности O(log(n)). Например, использование 4 уровней для списка пропуска с 16 узлами, 20 уровней для 1 миллиона узлов и 32 уровней для 4 миллиардов узлов обеспечивает временную сложность, аналогичную RB-дереву.

Пропустить список лучше по следующим причинам:

• Простота реализации. Несмотря на схожие характеристики с RB-деревом, его гораздо проще реализовать и поддерживать.

• Высокая эффективность добавления новых узлов в конец списка пропуска.

• Создать потокобезопасную реализацию списка пропуска проще, чем дерево.

Давайте рассмотрим реализацию этой концепции!

Узлы структуры:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

Функция для создания узлов:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

Во время вставки в задачу входит определение правильного места для хранения узла и определение количества уровней для подключения к этому узлу. Использование случайной функции для определения уровней помогает упростить процесс для каждого нового узла. В среднем эта функция выделяет второй уровень в 50% случаев, третий уровень в 25% случаев и так далее. Этот метод минимизирует время доступа к памяти для перебалансировки элементов.

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

Функция поиска узлов:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

Эталонная функция для проверки производительности связанного списка, списка пропуска и дерева RB. Значения, используемые в качестве ключей, задаются как степени двойки. Значение для целей тестирования не имеет значения.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

Результаты тестирования данной структуры данных на последовательно растущих ключах:

Это лучшее время для вставки (если не учитывать простой связанный список) и достаточно быстрый способ поиска элементов.

Результаты тестирования данной структуры данных на последовательно убывающих ключах:

Это легко понять: эта реализация списка пропуска имеет только указатель на первый элемент. Добавление узлов в конец является более сложным. Чтобы изменить этот подход, мы можем добавить второй указатель (в хвост) или обратный список пропуска (голова будет указывать на большие значения). Это означает, что список пропуска является эффективной структурой данных для данных журнала, таких как потоки Kafka. В этом случае оно может быть как минимум в два раза быстрее, чем дерево RB, и его будет проще реализовать.

Skip List снижает скорость вставки связанного списка, однако для последовательных данных он остается быстрее, чем другие структуры данных с логарифмическим временем доступа к элементам, особенно при последовательном росте ключей. Тем не менее, любой последовательный рост ключей усложняет вставку в дерево, поскольку требует большого количества вращений для поддержания баланса дерева.

Он работает эффективно только тогда, когда значение увеличивается (или уменьшается) на протяжении всей последовательности. Например, если мы рандомизируем ключи, результаты будут другими:

Как видно, распределение по значениям существенно не влияет на скоростные характеристики RB-дерева, но заметно влияет на производительность списка пропуска.

Выводы

Сегодня наши приложения могут организовывать данные в памяти или на диске по-разному. Карты и списки играют важную роль в упорядочивании данных в разном порядке для различных целей. Эти структуры обеспечивают достаточную производительность, эффективность использования ресурсов и возможности.

Иногда этого недостаточно для наших нужд, и приложение необходимо изменить в критических частях, чтобы оно было более оптимальным. В некоторых случаях может быть полезно использовать более подходящие структуры данных, такие как деревья для неточного сопоставления или экономии памяти. Другие — от усовершенствований алгоритма, например использования асинхронных методов для улучшения производительности отдельных потоков.

Когда все остальные варианты исчерпаны, остается вариант адаптировать структуру данных и скорректировать методологию использования. Есть примеры некоторых изменений в структуре данных, чтобы сделать их более подходящими для практически конкретной задачи.

Хотя связанный список в первую очередь представляет собой структуру данных только для записи и последовательного сканирования, его можно оптимизировать больше, чем дерево RB, и оставаться эффективным в случае только записи. Однако повышение одних характеристик может повлиять на другие. Поэтому лучший способ — расставить приоритеты в том, что важно, и отказаться от того, что неважно.