Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Описание [ править ]

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

 ... ABCDE ... -> следующий -> следующий -> следующий -> <- пред <- пред <- пред <-

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

 ... ABCDE ... <–> A⊕C <-> B⊕D <-> C⊕E <->

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

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

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

 т.е. адрес (D) = ссылка (C) ⊕ адрес (B) куда ссылка (C) = адрес (B) ⊕addr (D) так  адрес (D) = адрес (B) ⊕аддр (D) ⊕ адрес (B)   адрес (D) = адрес (B) ⊕аддр (B) ⊕ адрес (D)  поскольку  X⊕X = 0  => адрес (D) = 0 адрес (D) поскольку X⊕0 = х => адрес (D) = адрес (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). Инструкции для трансляции как System / 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 сложением или вычитанием дает несколько иные, но в значительной степени эквивалентные формулировки:

Добавить связанный список [ править ]

 ... ABCDE ... <–> A + C <-> B + D <-> C + E <->

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

Связанный список вычитания [ править ]

 ... ABCDE ... <–> CA <-> DB <-> EC <->

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

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

См. Также [ править ]

Ссылки [ править ]

[3]

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

Внешние ссылки [ править ]

  • Прокаш Синха, Двусвязный список с эффективным использованием памяти // LinuxJournal, 1 декабря 2004 г.