Связанный список XOR

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

Описание

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

 ... A        B        C         D         E ...
         –>  next –>  next  –>  next  –>
         <–  prev <–  prev  <–  prev  <–

Связанный список XOR сжимает одну и ту же информацию в одно поле адреса, сохраняя побитовое исключающее ИЛИ (здесь обозначенное ⊕) адреса предыдущего и адреса следующего в одном поле:

 ... A        B          C          D         E ...
         ⇌   A⊕C   ⇌   B⊕D   ⇌   C⊕E   ⇌

Более формально:

  link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...

При перемещении по списку слева направо: предположим, что курсор находится в позиции C, предыдущий элемент B может быть подвергнут операции XOR со значением в поле ссылки (B⊕D). После этого будет получен адрес D, и обход списка может возобновиться. Та же самая закономерность применима и в другом направлении.

то есть addr(D) = link(C) ⊕ addr(B) где

      link(C) = addr(B)⊕addr(D)

так

      addr(D) = addr(B)⊕addr(D) ⊕ addr(B)           
  
      addr(D) = addr(B)⊕addr(B) ⊕ addr(D)

с

       X⊕X = 0                 
       => addr(D) = 0 ⊕ addr(D)

с

       X⊕0 = X
       => addr(D) = addr(D)

Операция XOR отменяется addr(B) появляется в уравнении дважды, и все, что у нас остается, это addr(D).

Чтобы начать обход списка в любом направлении с некоторой точки, требуется адрес двух последовательных элементов. Если адреса двух последовательных элементов поменять местами, обход списка произойдет в противоположном направлении. ^[1]

Теория работы

Ключом является первая операция и свойства XOR:

X⊕X = 0
Х⊕0 = Х
X⊕Y = Y⊕X
(X⊕Y)⊕Z = X⊕(Y⊕Z)

Регистр R2 всегда содержит операцию XOR адреса текущего элемента C с адресом предшествующего элемента P: C⊕P. Поля Link в записях содержат XOR левого и правого адресов-преемников, например L⊕R. Исключающее ИЛИ R2 (C⊕P) с текущим полем ссылки (L⊕R) дает C⊕P⊕L⊕R.

Если предшественником был L, P(=L) и L сокращаются, оставляя C⊕R.
Если предшественником был R, P(=R) и R отменяются, оставляя C⊕L.

В каждом случае результатом является XOR текущего адреса со следующим адресом. XOR этого с текущим адресом в R1 оставляет следующий адрес. R2 остается с необходимой парой XOR текущего адреса и предшественника.

Функции

Для перехода от одного элемента к другому достаточно двух операций XOR, в обоих случаях достаточно одних и тех же инструкций. Рассмотрим список с элементами {…B C D…} причем R1 и R2 являются регистрами , содержащими, соответственно, адрес текущего элемента списка (скажем, C) и рабочим регистром, содержащим XOR текущего адреса с предыдущим адресом (скажем, C⊕D). Привести как инструкции System/360 :

X  R2,Link    R2 <- C⊕D ⊕ B⊕D (i.e. B⊕C, "Link" being the link field
                                  in the current record, containing B⊕D)
XR R1,R2      R1 <- C ⊕ B⊕C    (i.e. B, voilà: the next record)

Конец списка обозначается представлением элемента списка по нулевому адресу, расположенного рядом с конечной точкой, как в {0 A B C…}. Поле ссылки в A будет 0⊕B. В приведенной выше последовательности после двух операций XOR необходима дополнительная инструкция для обнаружения нулевого результата при определении адреса текущего элемента.
Конечную точку списка можно сделать отражающей, сделав указатель ссылки равным нулю. Нулевой указатель – это зеркало . (XOR адресов левого и правого соседей, будучи одинаковыми, равен нулю.)

Недостатки

Инструменты отладки общего назначения не могут следовать цепочке XOR, что усложняет отладку; ^[2]
Платой за уменьшение использования памяти является увеличение сложности кода, что делает обслуживание более дорогим;
Большинство схем сборки мусора не работают со структурами данных, которые не содержат литеральных указателей ;
Не все языки поддерживают преобразование типов между указателями и целыми числами, XOR для указателей не определяется в некоторых контекстах;
При перемещении по списку адрес узла, к которому ранее обращались, необходим для расчета адреса следующего узла, и указатели будут нечитаемыми, если не перемещаться по списку — например, если указатель на элемент списка содержался в других данных. структура;
Связанные списки XOR не предоставляют некоторых важных преимуществ двусвязных списков, таких как возможность удалить узел из списка, зная только его адрес, или возможность вставить новый узел до или после существующего узла, зная только адрес. существующего узла.

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

Вариации

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

Добавление связанного списка

 ...  A        B         C         D         E  ...
          ⇌   A+C   ⇌   B+D   ⇌   C+E   ⇌

Этот тип списка имеет те же свойства, что и связанный список XOR, за исключением того, что поле с нулевой ссылкой не является «зеркалом». Адрес следующего узла в списке определяется путем вычитания адреса предыдущего узла из поля ссылки текущего узла.

Связанный список вычитания

 ...  A        B         C         D         E  ...
          ⇌   C-A   ⇌   D-B   ⇌   E-C   ⇌

Этот тип списка отличается от стандартного «традиционного» связанного списка XOR тем, что последовательность инструкций, необходимая для перемещения по списку вперед, отличается от последовательности, необходимой для перемещения по списку в обратном направлении. Адрес следующего узла, идущего вперед, задается путем добавления поля ссылки к адресу предыдущего узла; адрес предыдущего узла определяется путем вычитания поля ссылки из адреса следующего узла.

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

Бинарное дерево поиска

Концепция связанного списка XOR может быть обобщена на двоичные деревья поиска XOR . ^[3]

См. также

Алгоритм обмена XOR

Ссылки

^ «Связный список XOR — двусвязный список с эффективным использованием памяти | Набор 1 — GeeksforGeeks» . Гики для Гиков . 23 мая 2011 г. Проверено 29 октября 2018 г.
^ Гадбуа, Дэвид; и др. «Часто задаваемые вопросы по GC [сборке мусора] – черновик» . Проверено 5 декабря 2018 г.
^ «Ассоциативные контейнеры C++ на основе дерева козла отпущения XOR» . Проверено 5 ноября 2021 г.

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

Прокаш Синха (1 декабря 2004 г.). «Двухсвязный список с эффективным использованием памяти» . Linux-журнал .
XORList: эффективный связанный список C++ (лицензия MIT)
Реализация Xor List на C++ в библиотеках Listes.

[1] «Связный список XOR — двусвязный список с эффективным использованием памяти | Набор 1 — GeeksforGeeks» . Гики для Гиков . 23 мая 2011 г. Проверено 29 октября 2018 г.

[2] Гадбуа, Дэвид; и др. «Часто задаваемые вопросы по GC [сборке мусора] – черновик» . Проверено 5 декабря 2018 г.

[3] «Ассоциативные контейнеры C++ на основе дерева козла отпущения XOR» . Проверено 5 ноября 2021 г.

[1]

[2]

[3]

v т и Структуры данных
Типы	Коллекция Контейнер
Абстрактный	Ассоциативный массив Мультикарта Структура поисковых данных Список Куча Очередь Двусторонняя очередь Приоритетная очередь Двусторонняя приоритетная очередь Набор Мультисет Непересекающееся множество
Массивы	Битовый массив Круговой буфер Динамический массив Хэш-таблица Дерево хешированного массива Разреженная матрица
Связано	Список ассоциаций Связанный список Пропустить список Развернутый связанный список Связанный список XOR
Деревья	B-дерево Бинарное дерево поиска АА-дерево АВЛ-дерево Красно-черное дерево Самобалансирующееся дерево Распространение дерева Куча Двоичная куча Биномиальная куча Куча Фибоначчи R-дерево Р* дерево R+ дерево Гильбертово R-дерево Трие Хэш-дерево
Графики	Бинарная диаграмма решений Ориентированный ациклический граф Направленный ациклический граф слов
Список структур данных