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

XOR linked list

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

Описание

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

 ... A B C D E ... -> следующая -> следующая -> следующая -> <- пред <- пред <- пред <-

Связанный список 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
  • X⊕0 = X
  • X⊕Y = Y⊕X
  • (X⊕Y) ⊕Z = X⊕ (Y⊕Z)

Регистр R2 всегда содержит операцию XOR адреса текущего элемента C с адресом предшествующего элемента P: C⊕P. Поля Link в записях содержат XOR левого и правого последующих адресов, например L⊕R. XOR 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). В ролях как Система / 360 инструкции:
X R2, Link R2 <- C⊕D ⊕ B⊕D (т.е. B⊕C, «Link» - поле ссылки в текущей записи, содержащее B⊕D) XR R1, R2 R1 <- C ⊕ B⊕C ( т.е. B, вуаля: следующая запись)
  • Конец списка обозначается представлением элемента списка с нулевым адресом, расположенного рядом с конечной точкой, как в {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 и традиционными связными списками.

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

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

[3]

  1. ^ "Связанный список XOR - двусвязный список с эффективным использованием памяти | Набор 1 - GeeksforGeeks". Гики. 2011-05-23. Получено 2018-10-29.
  2. ^ Гадбуа, Дэвид; и другие. "Вопросы и ответы по GC [сборке мусора] - черновик". Получено 5 декабря 2018.
  3. ^ Реализация Xor List на C ++ в библиотеке Listes.

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