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

Question

Я недавно наткнулся на ссылку, ниже которой я нашел довольно интересную.

http://en.wikipedia.org/wiki/XOR_linked_list

• Средства отладки общего назначения не может следовать цепочке XOR, делая более сложная отладка; [1]
• Цена за уменьшение памяти использование это увеличение кода сложность, делая обслуживание более дорогой;
• Большинство схем сбора мусора делают не работают со структурами данных, которые делают не содержит буквальных указателей;
• XOR указателей не определен в некоторые контексты (например, язык C), хотя многие языки предоставляют некоторые вид преобразования типа между указатели и целые числа;
• Указатели будут нечитаемыми, если никто не просматривает список - для пример, если указатель на список элемент содержался в других данных структура;
• При просмотре списка вам нужно запомнить адрес ранее доступ к узлу для того, чтобы рассчитать адрес следующего узла.

Теперь мне интересно, это исключительно для языков низкого уровня или это также возможно в C #?

Есть ли похожие варианты для получения таких же результатов с C #?

Answer 1

TL; DR Я быстро написал подтверждение концепции Реализация XorLinkedList в C #.

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

1. XorLinkedList должен быть "неуправляемой структурой", т. Е. Они не могут содержать управляемые ссылки
2. Из-за ограничения в обобщениях C # связанный список не может быть универсальным (даже с where T : struct)

Последнее, похоже, связано с тем, что вы не можете ограничить универсальный параметр неуправляемыми структурами . С помощью where T : struct вы также можете разрешить структуры, содержащие управляемые ссылки.

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

Низкоуровневое программирование на C #

private static Node* _ptrXor(Node* a, Node* b)
{
    return (Node*)((ulong)a ^ (ulong)b);//very fragile
}

Очень хрупкий, я знаю. Указатели C # и IntPtr не поддерживают XOR-оператор (вероятно, хорошая идея).

private static Node* _allocate(Node* link, int value = 0)
{
    var node = (Node*) Marshal.AllocHGlobal(sizeof (Node));
    node->xorLink = link;
    node->value = value;
    return node;
}

Не забудьте потом Marshal.FreeHGlobal эти узлы (Реализуйте полный шаблон IDisposable и убедитесь, что бесплатные вызовы размещены за пределами блока if(disposing).

private static Node* _insertMiddle(Node* first, Node* second, int value)
{
    var node = _allocate(_ptrXor(first, second), value);
    var prev = _prev(first, second);
    first->xorLink = _ptrXor(prev, node);
    var next = _next(first, second);
    second->xorLink = _ptrXor(node, next);
    return node;
}

Заключение

Лично я никогда не использовал бы XorLinkedList в C # (возможно, в C, когда я пишу действительно низкоуровневые системные вещи, такие как распределители памяти или структуры данных ядра. В любом другом случае небольшой выигрыш в эффективности хранения действительно не стоит боль. Тот факт, что вы не можете использовать его вместе с управляемыми объектами в C #, делает его практически бесполезным для повседневного программирования.

Кроме того, сегодня хранилище почти свободно, даже основная память, и если вы используете C #, вы, вероятно, не слишком заботитесь о хранилище. Я где-то читал, что заголовки объекта CLR были около 40 байтов, так что этот указатель будет наименьшим из ваших опасений;)

Answer 2

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

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

Другой вариант - использовать C ++ / CLI, который обеспечивает полную гибкость указателей, с одной стороны, и GC, а также доступ к инфраструктуре, когда она вам нужна, с другой.

Answer 3

Как альтернатива небезопасным решениям, которые были предложены.

Если вы подкрепили свой связанный список массивом или коллекцией списков, где вместо указателя памяти «следующий» и «предыдущий» указываются индексы в массиве, вы можете реализовать этот xor, не прибегая к небезопасным функциям.

Answer 4

C # обычно не позволяет вам манипулировать ссылками на этом уровне, поэтому, к сожалению, нет.

Answer 5

Делая широкое обобщение здесь: C #, кажется, прошел путь читабельности и чистых интерфейсов, а не путь битой игры и упаковки всей информации настолько плотно, насколько это возможно.

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

Answer 6

Возможно, однако, вы должны понимать, как C # смотрит на объекты.Переменная экземпляра на самом деле содержит не объект, а указатель на объект в памяти.

DateTime dt = DateTime.Now;

dt - указатель на структуру в памяти, содержащую схему DateTime.

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

Answer 7

Конечно.Вам просто нужно кодировать класс.оператор XOR в c # это ^ Это должно быть все, что вам нужно, чтобы начать кодирование.Обратите внимание, что для этого потребуется объявить код «небезопасным»См. здесь : как использовать указатели в c #.