XOR-связный список — @дневники: асоциальная сеть

19:19 XOR-связный список

Описано создание XOR-связного списка и его принципы работы. Описаны принципы работы динамических структур данных -- списков и деревьев (на примере двоичных деревьев).

В этой статье описывается создание так называемого XOR-связного списка, основаня идея которого заключается в том, что в каждом элементе списка хранятся не два адреса соседних элементов, а один псевдо-адрес, что является интересным алгоритмически решением и позволяет немного экономить память. Что такое указатель, объяснять не буду. Те, кто этого не знают, могут дальше не читать, им статья будет неинтересна.

(читать дальше)

1 Введение
1.1 Что такое динамические структуры данных?
При работе с самыми различным данными программисты часто сталкиваются с тем, что на момент компиляции программы неизвестно, с каким объёмом данных предстоит работать. Придётся обработать нам всего один байт или пять мегабайт? Нет ответа.
Хорошо, если данные хранятся в файле, их можно считывать кусками и нам пофиг, какого файл размера, лишь бы стандартные функции с ним работали. Иногда же приходится держать данные прямо в памяти. Однако многие компилируемые языки программирования не поддерживают возможность "на лету" изменять размеры массивов и подобных структур. Тут на помощь приходит динамическая память -- операционная система выдаёт куски памяти по запросу. Это является хорошим (и стандартным) решением, когда в определённый момент выполнения программы мы узнаём, сколько памяти нам нужно, и в дальнейшем этот объём не меняется.
Так тоже бывает не всегда. Зачастую объём хранимых данных меняется прямо во время выполнения программы. Что же делать? Один из способов -- выделить новую память, переписать туда новую версию данных, удалить старую память. Пока данных мало, всё хорошо, но как только их становится много, операции копирования начинают занимать слишком много времени.
Для работы с изменяющимся объёмами данных в памяти были придуманы так называемые "динамические структуры данных", позволяющие перемещаться по данным любого объёма, а также динамически менять общий объём данных не занимая полным копированием. Как этого можно достичь?
Допустим, все данные разбиты на некоторые логические куски -- "элементы". Они могут быть разного размера, однако по смыслу они должны быть одним и тем же. Например, целые числа, строки, картинки. Хороший и достаточно общий пример элемента -- экземпляр какого-либо класса.
Если мы для каждого элемента будем выделять память и складывать его туда, а при удалении освобождать память, которую он занимает, задача хранения данных будет решена (:, но непонятно, как по этим данным перемещаться. Можно, конечно, хранить указатели на каждый элемент в месте использования, ибо копировать-выделять массив указателей быстрее, чем совокупность всех элементов, но хотелось бы от этого копирования-выделения избавиться. Ключ к перемещению без полного копирования прост -- необходимо в каждом элементе хранить ссылки на ещё какие-то элементы (или на пустое место, если связи нет).
Типичные динамические структуры данных -- списки и деревья.
1.2 Что такое списки и деревья?
Поскольку основная часть посвящена спискам, начнём с деревьев, чтобы после списков перейти к основной теме.
1.2.1 Дерево
(показать про дерево; это оффтопик фактически, так что скрываю)
Оно называется дерево и имеет с ним некоторую аналогию. Дерево представляет собой ациклический граф. Подробнее об этом можно почитать в вики. Понятно, что дерево может быть n-ричным, но применительно к динамическим структурам данных будем рассматривать только двоичное дерево, как имеющее наибольшую практическую ценность. Не будем углубляться в математику, посмотрим просто как это работает. Забегая вперёд, скажу, что деревья очень хороши для поиска.

Обязательными полями для элемента двоичного дерева являются две ссылки на нижележащие элементы (будем называть их "левый" и "правый", хотя как называния, так и способ применения (см. ниже) не принципиальны, главное применять единообразно), а также так называемый "счётчик", на случай, если у нас будут несколько одинаковых элементов. Также необходимо придумать метод сравнения элементов, который должен отвечать следующим требованиям:
1. Если взять два произвольных элемента, один из них будет либо больше другого, либо меньше, либо равен.
2. Если два элемента по этому методу равны, то элементы являются полностью эквивалентными друг другу.
Другими словами, сравнение двух элементов "по размеру" не подходит, так как могут быть несколько элементов не эквивалентных друг другу, но имеющих одинаковый размер. Гораздо лучше сравнение по какому-либо хэшу (например, md5), но у элементов и хэши могут совпасть! (хотя это уже вряд ли). Тут уже надо кропотливо думать. Сравнивать числа и строки, правда, очень просто.
Признак, по которому мы сравниваем два элемента иногда называют "ключом" элемента.
Есть другой метод. Можно ввести только операцию "меньше", тогда элементы с повторным ключом будут неотличимы от элементов, которые больше. Это необходимо, если возможны различные элементы с одинаковыми ключами. Если такое невозможно (т.к. ключи всегда различны для различных элементов), то у нас будет потенциальное дублирование данных.

1.2.1.1 Заполнение дерева
Итак, в месте использования мы храним ровно один указатель на элемент, называемый "корнем дерева". Этот элемент либо есть, либо его нет. Если его нет, дерево пустое. Если мы добавляем элемент в пустое дерево, он становится корнем. Хотим добавить ещё один элемент и тут понимаем, что непонятно, как это следует сделать. Поскольку дерево двоичное, каждый элемент имеет по ДВА указателя на следующие элементы. Куда пихать? А если сделать так? Если новый элемент БОЛЬШЕ корневого, будем сохранять указатель на него СПРАВА (новый > старого, галочка смотрит вправо), а если МЕНЬШЕ -- СЛЕВА, а? Если место с этой стороны уже занято, перейдём по указателю и повторим процедуру с элементом ниже по уровню, пока не найдём пустое место. Если наткнёмся на элемент, который равен текущему, то останется только увеличить счётчик вхождений такого элемента на единицу.
Приведу пример заполнения.

Пример 1.
Итак, есть числа 7, 4, 9, 5, 2, 4, 3.


1. 7 -- идёт в корень.
Уровень 0.          7
2. 4<7. Кладём слева.
Уровень 0.          7
                   /
Уровень 1.        4
3. 9>7. Кладём справа.
Уровень 0.          7
                   / \
Уровень 1.        4   9
4. 5<7, но то место уже занято! Спускаемся к 4. 5>4 -- кладём справа от 4.
Уровень 0.         7
                  / \
Уровень 1.       4   9
                  \
Уровень 2.         5
5. 2<7, 2<4.
Уровень 0.         7
                  / \
Уровень 1.       4   9
                / \
Уровень 2.     2   5
5. 4<7, 4=4. Увеличиваем ссылку
Уровень 0.         7
                  / \
Уровень 1.       4(2)9
                / \
Уровень 2.     2   5
6. 3<7, 3<4, 3>2.
Уровень 0.         7
                  / \
Уровень 1.       4(2)9
                / \
Уровень 2.     2   5
                \
Уровень 3.       3

Как заполнять дерево, вроде понятно. А как удалять?
1.2.1.2 Удаление элемента из дерева
а) если счётчик больше 1, просто уменьшаем его
б) Если мы хотим удалить элемент, у которого нет ссылок на более нижние уровни, всё понятно -- данные удаляются, ссылка, которая ссылалась на него, устанавливается в значение "пусто".
в) Если только с одной стороны есть более нижние уровни, элемент удаляем, единственный из двух возможных более нижних элементов, прицепляем вместо удалённого, чтобы верхний ссылался на него.
г) Если есть оба более нижних элемента, всё становится печально. Надо найти им новый родительский элемент, при этом следует учесть, что нельзя нарушить порядка больше-меньше, иначе дерево потеряет смысл (о смысле см. далее). Кто же подойдёт на эту роль? Элемент должен быть меньше любого элемента справа, но больше любого элемента слева! Найдём самый левый элемент правого поддерева. Это -- его наименьший элемент. Если его удалить по вышеописанному алгоритму (тут понятно, что один из пунктов "б","в" сработает, ибо "г" бы означал, что это не самый левый элемент, про пункт "а" см. далее)), спрятав данные у себя, то он станет меньше любого элемента в правом поддерева. А то, что он больше любого элемента левого поддерева и так понятно, ведь иначе бы он в нём и находился! Следует учесть, что забирать данные надо вместе со счётчиком а удалять надо все экземпляры (поэтому удаление по пункту "а" никогда не будет), ибо если перенести только один экземлпяр, у нас будет несколько равных элементов в разных местах, этого быть не должно. Данные удаляемого элемента удаляем, а спрятанные пишем вместо них. Вуаля.
Пример 2.


Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         6   9
                    \
Уровень 3.           7
Хотим удалить корень дерева.
1. Придётся работать по пункту "г". В правом поддереве самый левый элемент это 6, копируем к себе (6) и удаляем (работает пункт "в").
Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         7   9
2. Удаляем данные корня, вместо них пишем то, что было в загашнике.
Уровень 0.         6
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         7   9
Как видно, порядок больше-меньше не нарушился.

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

Пример 3.
Допустим, в дереве из предыдущего примера (до удаления) хотим найти 7.


Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         6   9
                    \
Уровень 3.           7

1. 7>5, перешли вправо.
2. 7<8, перешли влево.
3. 7>6, перешли вправо. Вот оно! Конец.
Разумеется, в нашем примере такой поиск бессмысленен и беспощаден, поскольку наши данные и есть ключ. Если же к нашему числу прилеплено ещё пять мегабайт фигни, смысл очень большой:
1. Мы сравниваем данные только по ключам, а не целиком.
2. Мы просматриваем только часть данных (3 проверки при 6 элементах).
Если надо пробежать по всем элементам, делается это следующим образом.
1. Сначала обрабатываем всё, что слева, потом себя, потом всё, что справа.
2. Спустившись на уровень ниже, повторяем пункт 1.
Понятно, что мы имеем дело с рекурсией и понятно, что мы обработаем данные в порядке возрастания. Аналогично можно придумать обработку и в порядке убывания.
Менее кустарно об этом можно прочитать тут.

К достоинствам дерева можно отнести авто-упорядочивание и быстрый поиск.
К недостаткам относится наличие рекурсии (вы заметили? (: ), что ведёт к неконтролируемому использованию стека.
К потенциальным недостаткам можно отнести следующую ситуацию. При добавлении уже упорядоченных данных, они будут добавляться всё время с одной и той же стороны дерева, превращая её В СПИСОК (см. далее)! Это называется "разбалансировка", лечится "балансировкой". Короче, надо следить, чтобы дерево было сбалансированным, т.е. слева и справа примерно одинаковое число элементов.

1.2.2 Списки
Список -- это проще чем дерево. (: В списке все элементы хранятся последовательно, при этом в каждом есть одна или две ссылки на другие элементы.
По направленности списки делятся на:
-- однонаправленные;
-- двунаправленные.
По цикличности списки делятся на
-- циклические (циклические);
-- ациклические (= (линейные).
В однонаправленных ссылка одна и перемещаться можно только вперёд. Как акула. В месте использования надо хранить указатель на один из элементов, желательно первый (а если список ациклический, то обязательно на первый!).
В двунаправленных ссылки две -- на предыдущий и на следующий элемент.
В циклических списках последний элемент ссылается на первый, в ациклических у последнего в ссылке на следующий стоит "пусто" и у первого в ссылке на предыдущий (если она есть) стоит "пусто". Необходимость использования того или иного типа списка определяется формулировкой задачи.
Добавление элемента в список (в конец или в середину) заключается в следующем:
1. Указатель "следующий" старого-предыдущего (если он есть) элемента начинает указывать на новый;
2. Указатель "предыдущий" (если он есть) старого-следующего элемента (если он есть) начинает указывать на новый;
3. Указатели "следующий" и "предыдущий" (если они есть) нового начинают указывать на старый-следующий и старый-предыдущий соответственно.
Если следующего/предыдущего элемента нет, в соответствующие указатели нового элемента устанавливается "пусто".
Удаление происходит следующим образом.
1. Указатель "следующий" предыдущего элемента начинают указывать на следующий после удаляемого элемент (если он есть; иначе -- "пусто");
2. Указатель "предыдущий" (если он есть) следующего элемента (если он есть) начинает указывать на предыдущий перед удаляемым элемент (если он есть; иначе -- "пусто");
3. Удаляемый элемент удаляется и идёт лесом.
Перемещение по списку превращается в детскую забаву -- знай себе, переходи по указателю.
А поиск только последовательным просмотром. Такие дела.
2 XOR-связный список
2.1 Что такое XOR и с чем его едят
С давних времён в программировании и дискретной математике применяются логические (в том числе побитовые) операции. XOR ("исключающее или", "сложение по модулю два", "строгая дизъюнкция" -- одна из них, причём она обладает некоторыми интересным свойствами. Таблица истинности для неё выглядит следующим образом:


+-------+-------+-------+
| x1\x2 |Истина |Ложь   |
+-------+-------+-------+
|Истина |Ложь   |Истина |
+-------+-------+-------+
|Ложь   |Истина |Ложь   |
+-------+-------+-------+

Другими словами, для двух логических значений x1 и x2 на выходе "истина", если истенен только один из операндов. Если оба истинны или оба ложны, получается ложь.
2.2 Что такое побитовая операция
Операция с двумя операндами называется побитовой, если она проводится над соответствующими битами обоих операндов и записывается в бит с тем же самым номером на выход, при этом соседние биты не затрагиваются.
Пример 4.
Вычислим побитовое XOR двух двоичных чисел (8-битных байт):


01110010
11010001
-------
10100011

2.3 Области применения XOR
Ну, во первых, это несложное шифрование. Пусть есть сообщение A и ключ шифрования K такой же длины (в битах). Проведём XOR:
A XOR K =A1.
Очевидно, что если ключ ненулевой, то на выходе будет не то же, что на входе, т.е. данные изменились. Как их достать обратно? Проведём XOR тем же ключом ещё раз!
((A XOR K) XOR K) = A XOR (K XOR K) = A XOR 0 = A.
Получили исходное значение.
K XOR K = 0, поскольку одинаковые биты первого и второго операнда зануляются (таблица истинности, см. 2.1), а они все одинаковые, значит на выходе 0.
A XOR 0 = A, поскольку XOR и истины и лжи с ложью равен исходному значению по таблице истинности, а второе значение состоит целиком и лжи (нолики).
Пример 5.


01110010 -- сообщение
11010001 -- ключ
-------
10100011 -- зашифрованное сообщение
----------------------------------------------
10100011 -- зашифрованное сообщение
11010001 -- ключ
--------
01110010 -- исходное сообщение

Вторая область применения -- это зануление. Дело в том, что операция переноса данных в процессоре гораздо медленнее, чем логическая. Сделать же регистр равным нулю -- довольно распространённая задача. Если решать в лоб, то надо делать так:

MOV AX, 0

Если подумать, то быстрее делать так:

XOR AX, AX

Что исключающее или числа самого с собой равно нулю, мы выяснили выше.
Некоторые процессоры, однако, имеют встроенную команду зануления регистра.
Может быть можно ещё что-нибудь интересное придумать с XOR?
2.4 Применимость XOR к двунаправленным спискам.
Давайте возьмём случай с шифрованием, и рассмотрим один интересный момент:
если сделать XOR между исходным сообщением и зашифрованным, получается ключ! Смотрите:
A XOR A1= A XOR (A XOR K)= (A XOR A) XOR K = 0 XOR K = K.
Теперь давайте вместо A, A1, K писать C1, C2, U (соответственно). Получим:
C1 XOR C2 = U
U XOR C1 = C2
U XOR C2 = C1
Что же получается-то? Если у нас есть два абстрактных числа, то зная их XOR и одно из чисел, можно найти второе.

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

Итак, пусть у нас есть пять элементов, при этом их адреса будем обозначать A_i, а ежи -- U_i.
Жирным обозначено, когда связь переходит через конец списка, палочки обозначают XOR чего и чего в еже. Кружочки -- сами элементы.


     A1   A2   A3   A4   A5
   \ O / \O / \O / \O / \O /
     U1   U2   U3   U4   U5

Во избежание проблем будем считать список циклически. Тогда:
U1 = A5 XOR A2
U2 = A1 XOR A3
U3 = A2 XOR A4
U4 = A3 XOR A5
U5 = A4 XOR A1

Пусть нам известны адреса 3 и 4 элемента. Мы хотим узнать, что было до и после них.
До: берём ёж третьего элемента и делаем исключающее или с адресом четвёртого:
U3 XOR A4 = (A3 XOR A4) XOR A4 = A3 XOR (A4 XOR A4) = A3.
После: берём ёж четвёртого элемента и делаем исключающее или с адресом третьего:
U4 XOR A3 = (A3 XOR A5) XOR A3 = A5 XOR (A3 XOR A3) = A5.
Оно работает!
А как добавить элемент?
Хотим добавить элемент X после A2.
Ёж нового элемента -- это просто исключающее или его новых соседей. А вот их ежи придётся пересчитать:
UX= A2 XOR A3
U2'=A1 XOR AX
U3'=AX XOR A4


     A1   A2   AX   A3   A4   A5
   \ O / \O / \O / \O / \O / \O /
     U1   U2'  UX   U3'  U4   U5

Ещё тонкий момент -- удаление элемента. Удалим A2. Необходимо пересчитать ежи.
U1'=U5 XOR AX
UX'= U1 XOR A3


    A1   AX   A3   A4   A5
  \ O / \O / \O / \O / \O /
    U1'  UX'  U3'  U4   U5

Разумеется в программе всё чуть сложнее.

2.5 Ежиная арифметика
Адрес XOR Адрес = Ёж
Ёж XOR Адрес = Адрес
Адрес XOR Ёж = Адрес
Ёж XOR Ёж =? Не имеет смысла

2.6 Особенности XOR-связного списка
1. Поскольку надо знать сразу два элемента (последовательных), вместо одного указателя на текущий элемент списка, придётся хранить ещё указатель на следующий (предыдущий).
2. Усложнённая арифметика: навигация по списку становится дольше.
3. В каждом элементе хранится только один ёж, а не два адреса, поэтому можно экономить память. Нужна ли такая экономия -- зависит от формулировки задачи.

2.7 Реализация алгоритма
Проще всего организовать класс, который будет всем этим заниматься. Пример реализации такого класса вместе с демонстрационной программой представлен в Приложении 1.

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

Приложение 1. Пример реализации класса XOR-связного списка на C++
pastebin (cpp)
mediafire (exe)

Статья написана по просьбе того, кто знает (:.

@темы: Программы, Программирование, Тухлые идеи, Статьи