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

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

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

Обзор

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

 записывать node { узел Следующий // ссылка на следующий узел в списке     int numElements // количество элементов в этом узле, до maxElements     массив элементы // массив элементов numElements,                     // с пространством, выделенным для элементов maxElements }

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

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

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

Спектакль

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

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

Затем пространство, используемое для п элементы варьируются между и . Для сравнения, обычные связанные списки требуют пространство, хотя v может быть меньше, и массивы, одна из самых компактных структур данных, требует Космос. Развернутые связанные списки эффективно распределяют накладные расходы v над рядом элементов списка. Таким образом, мы видим наиболее значительный выигрыш в пространстве при больших накладных расходах, maxElements большой или мелкие элементы.

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

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

Смотрите также

  • CDR кодирование, еще один метод уменьшения накладных расходов и улучшения локализации кэша в связанных списках, подобных развернутым связанным спискам.
  • то пропустить список, аналогичный вариант связанного списка, предлагает быстрый поиск и вредит преимуществам связанных списков (быстрая вставка / удаление) меньше, чем развернутый связанный список
  • то B-дерево и Т-образное дерево, структуры данных, похожие на развернутые связанные списки в том смысле, что каждую из них можно рассматривать как «развернутое двоичное дерево»
  • Связанный список XOR, двусвязный список, который использует один указатель XOR на узел вместо двух обычных указателей.
  • Дерево хешированных массивов, где указатели на блоки данных хранятся в отдельном массиве более высокого уровня.

Рекомендации

  • Shao, Z .; Реппи, Дж. Х .; Аппель, А. В. (1994), «Раскрутка списков», Запись конференции 1994 ACM Conference on Lisp and Functional Programming: 185–191, Дои:10.1145/182409.182453, ISBN  978-0897916431CS1 maint: ref = harv (ссылка на сайт)

внешняя ссылка