Ответ 1

Я знаю, что это мой второй ответ, но я думаю, что объяснение, которое я здесь даю, может быть лучше, чем последний ответ. Но обратите внимание, что даже этот ответ правильный.

A Эффективный связанный с памятью список чаще всего называется XOR Linked List, поскольку он полностью зависит от логического Gate XOR и его свойства.

Отличается ли он от двусвязного списка?

Да, это так. Он фактически выполняет почти ту же работу, что и Doubly Linked List, но он отличается.

A Doubly-Linked List хранит два указателя, которые указывают на следующий и предыдущий node. В принципе, если вы хотите вернуться, вы перейдете к адресу, указанному указателем back. Если вы хотите идти вперед, вы переходите к адресу, указанному указателем next. Это нравится:

A Связанный с памятью список ссылок, а именно Связанный список XOR имеет только один указатель вместо двух. В этом сохранен предыдущий адрес (addr (prev)) XOR (^) следующий адрес (addr (следующий)). Когда вы хотите перейти к следующему node, вы выполняете определенные вычисления и находите адрес следующего node. Это то же самое для перехода к предыдущему node. Это похоже на:

Как это работает?

Связанный список XOR, как вы можете понять из его имени, сильно зависит от логического элемента XOR (^) и его свойств.

Его свойства:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

Теперь оставьте это в стороне и посмотрите, что хранит каждый node:

Первая node или head хранит 0 ^ addr (next), поскольку нет предыдущего node или адреса. Это выглядит так:

Затем второй node хранит addr (prev) ^ addr (next). Это выглядит так:

На рисунке выше изображен node B, или второй node. A и C - адрес третьего и первого node. Все node, кроме головы и хвоста, как и предыдущие.

хвост списка, не имеет следующего node, поэтому он сохраняет addr (prev) ^ 0. Это выглядит так:

Прежде чем увидеть, как мы движемся, снова увидим представление связанного списка XOR:

Когда вы видите

это явно означает, что есть одно поле ссылки, с помощью которого вы двигаетесь назад и вперед.

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

Переход от главы к следующему node

Скажем, теперь вы находитесь на первом node или в node A. Теперь вы хотите перейти на node B. Это формула для этого:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Итак, это будет:

addr (next) = addr (prev) ^ (0 ^ addr (next))

Поскольку это голова, предыдущий адрес был бы просто 0, поэтому:

addr (next) = 0 ^ (0 ^ addr (next))

Мы можем удалить круглые скобки:

addr (next) = 0 ^ 0 addr (next)

Используя свойство none (2), мы можем сказать, что 0 ^ 0 всегда будет 0:

addr (next) = 0 ^ addr (next)

Используя свойство none (1), мы можем упростить его:

addr (next) = addr (next)

Вы получили адрес следующей node!

Переход от node к следующему node

Теперь скажем, что мы находимся в середине node, который имеет предыдущий и следующий node.

Применим формулу:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Теперь замените значения:

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

Удалить круглые скобки:

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

Используя свойство none (2), мы можем упростить:

addr (next) = 0 ^ addr (next)

Используя свойство none (1), мы можем упростить:

addr (next) = addr (next)

И получишь!

Переместившись с node на node, вы были в предыдущем

Если вы не понимаете заголовок, это в основном означает, что если вы были в node X и теперь переместились на node Y, вы хотите вернуться к node, посещенному ранее, или в основном node X.

Это не громоздкая задача. Помните, что я упомянул выше, что вы храните адрес, на котором вы были во временной переменной. Таким образом, адрес node, который вы хотите посетить, лежит в переменной:

addr (prev) = temp_addr

Переход от node к предыдущему node

Это не то же самое, что указано выше. Я хочу сказать, что вы были в node Z, теперь вы находитесь в node Y и хотите перейти к node X.

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

Я не думаю, что мне нужно это объяснить.

Преимущества связанного списка XOR

• Это использует меньше памяти, чем Doubly Linked List. Приблизительно на 33% меньше.

• Используется только один указатель. Это упрощает структуру node.

• Как сказал дойнакс, подрежим XOR можно поменять на противоположное по времени.

Недостатки связанного списка XOR

• Это немного сложно реализовать. Он имеет более высокие шансы на сбой, и отладка довольно сложная.

• Все преобразования (в случае int) должны выполняться в /from uintptr_t

• Вы не можете просто получить адрес node и начать перемещение (или что-то еще) оттуда. Вы всегда должны начинать с головы или хвоста.

• Вы не можете прыгать или пропускать узлы. Вы должны идти один за другим.

• Для перемещения требуется больше операций.

• Трудно отлаживать программу, использующую связанный список XOR. Намного проще отлаживать двойной список.

Ссылки

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

Ответ 2

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

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

В реализации с уменьшенной памятью вы заменяете "next" и "prev" на одно значение, которое является побитовым исключением-OR (побитовое-XOR) "next" и "prev" . Поэтому вы уменьшаете хранилище для смежных указателей элементов на одну половину.

Используя этот метод, по-прежнему можно перемещать список в любом направлении, но для этого вам нужно знать адрес предыдущего (или следующего) элемента. Например, если вы перемещаете список в прямом направлении, и у вас есть адрес "prev" , вы можете получить "следующий", взяв бит-XOR "prev" с текущим комбинированным значением указателя, который "prev" XOR "next" . Результатом является "prev" XOR "prev" XOR "next" , который просто "следующий". То же самое можно сделать в обратном направлении.

Недостатком является то, что вы не можете делать такие вещи, как удаление элемента, указав указатель на этот элемент, не зная адрес элемента "prev" или "next" , поскольку у вас нет контекста для декодирования комбинированное значение указателя.

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

Это умный трюк, но, честно говоря, я вижу очень мало причин использовать его в наши дни.

Ответ 3

Я бы рекомендовал увидеть мой второй ответ на этот вопрос, поскольку он намного яснее. Но я не говорю, что этот ответ неверен. Это также правильно.

A Эффективный связанный с памятью список также называется XOR Linked LIST.

Как это работает

A XOR (^) Связанный список - это список ссылок, в котором вместо хранения указателей next и back мы просто используем указатель один, чтобы сделать задание указателей next и back. Сначала рассмотрим свойства логических ворот XOR:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

Теперь возьмем пример. У нас есть двойной список с четырьмя узлами: A, B, C, D. Вот как это выглядит:

Если вы видите, каждый node имеет два указателя и 1 переменную для хранения данных. Поэтому мы используем три переменные.

Теперь, если у вас есть Doubly Linked List с большим количеством узлов, память, которую он будет использовать, будет слишком большой. Чтобы сделать его более эффективным, мы используем Эффективный двунаправленный список с памятью.

A Эффективный двунаправленный список с памятью - это связанный список, в котором мы используем только один указатель для перемещения вперед и назад с использованием свойств XOR и его свойств.

Здесь изобразительное представление:

Как вы двигаетесь назад и вперед?

У вас есть временная переменная (только одна, а не node). Скажем, вы пересекаете node слева направо. Итак, вы начинаете с node A. В указателе node A вы храните адрес node B. Затем переходите к node B. Переходя к node B, во временной переменной вы храните node адрес A.

Переменная link (указатель) node B имеет адрес A ^ C. Вы бы взяли предыдущий адрес node (который есть A) и XOR он с текущим полем ссылки, указав адрес C. Логически это выглядело бы так:

A ^ (A ^ C)

Теперь упростим уравнение. Мы можем удалить круглые скобки и переписать их из-за ассоциативного свойства:

A ^ A ^ C

Мы можем упростить это для

0 ^ C

из-за второго (свойство "Нет (2)" как указано в таблице ".

Из-за первого (свойство "None (1)" как указано в таблице "это в основном

C

Если вы не можете все это понять, просто посмотрите третье свойство ( "None (3)", как указано в таблице).

Теперь вы получили адрес node C. Это будет тот же процесс для возврата.

Скажем, что вы перешли от node C к node B. Вы сохранили бы адрес node C во временной переменной, повторите описанный выше процесс.

ПРИМЕЧАНИЕ. Все, как A, B, C, являются адресами. Спасибо Батшеве за то, что он сказал мне, чтобы я дал понять.

Недостатки связанного списка XOR

• Как упоминал Лундин, все преобразования должны выполняться от/до uintptr_t.

• Как сказал Сами Кухмона, вы должны начать с четко определенной начальной точки, а не только с произвольной node.

• Вы не можете просто прыгать node. Вы должны идти в порядок.

Также обратите внимание, что связанный список XOR не является лучше, чем двусвязный список в большинстве случаев.

Ссылки

• https://en.wikipedia.org/wiki/XOR_linked_list
• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
• http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

Ответ 4

ОК, поэтому вы видели связанный список XOR, который сохраняет один указатель на элемент... но это уродливая, уродливая структура данных и далеко не все, что вы можете сделать.

Если вы беспокоитесь о памяти, почти всегда лучше использовать двусвязный список с более чем 1 элементом на node, как связанный список массивов.

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

В дополнение к экономии памяти вы получаете преимущества в локальности, поскольку все 16 элементов в node находятся рядом друг с другом в памяти. Алгоритмы, проходящие через список, будут быстрее.

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

Существует множество возможных стратегий для определения того, как и когда выделять или освобождать узлы.

Ответ 5

У вас уже есть довольно подробное объяснение связанного списка XOR, я поделюсь еще несколькими идеями по оптимизации памяти.

• Указатели обычно принимают 8 байтов на 64-битных машинах. Необходимо обращаться к любой точке в ОЗУ, превышающей 4 ГБ, с 32-разрядными указателями.

• Менеджеры памяти обычно занимаются блоками фиксированного размера, а не байтами. Например. C malloc обычно выделяет в пределах 16 байт гранулярности.

Эти две вещи означают, что если ваши данные равны 1 байт, соответствующий элемент с двойным соединением будет принимать 32 байта (8 + 8 + 1, округленный до ближайшего 16 кратных). С трюком XOR вы можете получить его до 16.

Однако, чтобы еще больше оптимизировать работу, вы можете использовать свой собственный менеджер памяти, который: (а) имеет дело с блоками с меньшей гранулярностью, например, 1 байт или, может быть, даже переходит в бит, (b) имеет более строгие ограничения на общий размер. Например, если вы знаете, что ваш список всегда будет входить в непрерывный блок размером 100 МБ, вам нужно всего лишь 27 бит для обращения к любому байту внутри этого блока. Не 32 или 64 бит.

Если вы не разрабатываете общий класс списка, но знаете конкретные шаблоны использования для своего приложения, во многих случаях реализация такого менеджера памяти может быть легкой задачей. Например, если вы знаете, что никогда не будете выделять более 1000 элементов, и каждый элемент занимает 5 байтов, вы можете реализовать диспетчер памяти как 5000-байтовый массив с переменной, которая содержит индекс первого свободного байта, а поскольку вы выделяете дополнительный элемент, вы просто берете этот индекс и перемещаете его вперед по выделенному размеру. В этом случае ваши указатели не будут действительными указателями (например, int *), а будут только индексами внутри этого 5000-байтового массива.