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

В этой модели максимальное количество элементов — 4 для каждого узла.

В компьютерном программировании развернутый связанный список — это разновидность связанного списка , в каждом узле которого хранится несколько элементов. Это может значительно повысить производительность кэша , одновременно уменьшив нагрузку на память, связанную с хранением метаданных списков, таких как ссылки . Это связано с B-деревом .

Обзор

Типичный узел развернутого связанного списка выглядит следующим образом:

 record node {
     node next       // reference to next node in list
     int numElements // number of elements in this node, up to maxElements
     array elements  // an array of numElements elements,
                     //   with space allocated for maxElements elements
 }

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

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

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

Производительность

Одним из основных преимуществ развернутых связанных списков является снижение требований к хранилищу. Все узлы (кроме не более одного) заполнены как минимум наполовину. Если выполнено много случайных вставок и удалений, средний узел будет заполнен примерно на три четверти, а если вставки и удаления выполняются только в начале и конце, почти все узлы будут заполнены. Предположим, что:

• м = maxElements, максимальное количество элементов в каждом elements множество;
• v = накладные расходы на узел для ссылок и количества элементов;
• s = размер одного элемента.

Тогда пространство, используемое для n элементов, варьируется в пределах $(v/m+s)n$ и $(2v/m+s)n$. Для сравнения, обычные связанные списки требуют $(v+s)n$ пространство, хотя v может быть меньше, а массивы , одни из самых компактных структур данных, требуют $sn$ космос. Развернутые связанные списки эффективно распределяют накладные расходы v на несколько элементов списка. Таким образом, мы видим наиболее значительный выигрыш в пространстве при больших накладных расходах. maxElements большой или элементы маленькие.

Если элементы особенно малы, например биты, накладные расходы могут быть в 64 раза больше, чем данные на многих машинах. Более того, многие популярные распределители памяти сохраняют небольшой объем метаданных для каждого выделенного узла, увеличивая эффективные накладные расходы v . И то, и другое делает развернутые связанные списки более привлекательными.

Поскольку каждый узел развернутого связанного списка хранит счетчик рядом со следующим полем, извлечение k -го элемента развернутого связанного списка (индексирование) может быть выполнено за n / m + 1 промах в кэше, что в m раз лучше, чем в обычном связанном списке. списки. Кроме того, если размер каждого элемента мал по сравнению с размером строки кэша, список можно пройти по порядку с меньшим количеством промахов в кэше, чем в обычных связанных списках. В любом случае время операции по-прежнему увеличивается линейно с размером списка.

См. также

• CDR-кодирование
• Пропустить список
• Т-образное дерево
• Связанный список XOR
• Дерево хешированного массива

Ссылки

• Шао, З.; Реппи, Дж. Х.; Аппель, AW (1994), «Развертывание списков», Материалы конференции ACM 1994 года по LISP и функциональному программированию - LFP '94 , стр. 185–191 , doi : 10.1145/182409.182453 , ISBN  978-0897916431 , S2CID   3192876

Внешние ссылки

• Реализация написана на C
• Другая реализация, написанная на Java.
• Реализация написана на Golang.
• Структуры открытых данных — Раздел 3.3 — SEList: Компактный связанный список , Пэт Морин