6

我最近遇到了下面的链接，我发现它很有趣。

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

  • 通用调试工具不能遵循异或链，调试难度较大；[1]
  • 内存使用量减少的代价是代码复杂度的增加，使得维护成本更高；
  • 大多数垃圾收集方案不适用于不包含文字指针的数据结构；
  • 在某些上下文（例如，C 语言）中没有定义指针的异或，尽管许多语言提供了指针和整数之间的某种类型转换；
  • 如果不遍历列表，则指针将不可读——例如，如果指向列表项的指针包含在另一个数据结构中；
  • 在遍历列表时，您需要记住先前访问的节点的地址，以便计算下一个节点的地址。

现在我想知道这是否是低级语言独有的，还是在 C# 中也可以？

是否有任何类似的选项可以使用 C# 产生相同的结果？

4

7 回答 7

8

TL;DR我很快用 C# 编写了一个概念验证的XorLinkedList 实现。

在 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;
}

结论

就个人而言，我永远不会在 C# 中使用 XorLinkedList（也许在 C 中，当我在编写内存分配器或内核数据结构等非常低级的系统内容时。在任何其他设置中，存储效率的小幅提升确实不值得痛苦。事实上，你不能将它与 C# 中的托管对象一起使用，这使得它对于日常编程几乎毫无用处。

今天，存储几乎是免费的，即使是主内存，如果你使用 C#，你可能不太关心存储。我在某处读到 CLR 对象标头大约为 40 个字节，因此这个指针将是您最不关心的问题；）

于 2011-05-13T13:40:01.477 回答
1

C# 通常不允许您在该级别操作引用，所以很遗憾。

于 2011-05-12T21:09:47.113 回答
1

作为已提出的不安全解决方案的替代方案。

如果您使用数组或列表集合来支持您的链表，而不是内存指针“下一个”和“上一个”指示数组的索引，您可以实现此异或，而无需使用不安全的功能。

于 2011-05-12T21:27:28.873 回答
1

在 C# 中有多种方法可以使用指针，但您只能临时拥有指向对象的指针，因此您不能在这种情况下使用它们。造成这种情况的主要原因是垃圾收集——只要你可以做一些异或指针之类的事情，然后再对它们进行异或，GC 就无法知道收集某个对象是否安全。

您可以通过在一个大数组中使用索引来模拟指针来制作非常相似的东西，但是您必须自己实现一种简单的内存管理形式（即，当创建新节点时，我应该将它放在数组的哪个位置？）。

另一种选择是使用 C++/CLI，它一方面允许您完全灵活地使用指针，另一方面允许 GC 和在需要时访问框架。

于 2011-05-12T21:29:11.637 回答
0

当然。你只需要编写类。c# 中的 XOR 运算符是 ^ 这应该是您开始编码所需的全部内容。请注意，这将要求将代码声明为“不安全”。请参阅此处：了解如何在 c# 中使用指针。

于 2011-05-12T21:10:54.290 回答
0

在这里做一个广泛的概括：C# 似乎走的是可读性和干净接口的道路，而不是位摆弄和尽可能密集地打包所有信息的道路。

因此，除非您在这里有特殊需要，否则您应该使用您提供的列表。未来的维护程序员会感谢你的。

于 2011-05-12T21:38:06.403 回答
-4

但是，您可能必须了解 C# 如何看待对象。实例变量实际上并不包含对象，而是指向内存中对象的指针。

DateTime dt = DateTime.Now;

dt 是指向内存中包含 DateTime 方案的结构的指针。

所以你可以做这种类型的链表，虽然我不确定你为什么会这样做，因为框架通常已经实现了最有效的集合。作为一种思想实验，这是可能的。

于 2011-05-12T21:20:28.900 回答