如何在 Python 中实现 XOR 链表? [英] How to implement an XOR Linked List in Python?
问题描述
鉴于python对象只是对实际内存对象的引用，并且无法检索对象的内存地址.
Given that python objects are only a reference to the actual memory Objects and memory address of objects cannot be retrived.
是否可以在 Python 中实现 XOR 链表?如果是，如何?
Is it possible to implement an XOR linked list in Python ? if yes how ?
推荐答案
您不能在 Python 中构建 XOR 链表，因为 Python 不允许您弄乱指针中的位.
You can't build an XOR linked list in Python, since Python doesn't let you mess with the bits in pointers.
无论如何你都不想实现它——这是一个肮脏的把戏，它使你的代码难以理解，而且收益甚微.
You don't want to implement that anyway -- it's a dirty trick that makes your code hard to understand for little benefit.
如果您担心内存，那么使用每个节点超过 1 个元素的双向链表几乎总是更好，例如数组的链表.
If you're worried about memory, it's almost always better to use a doubly-linked list with more than 1 element per node, like a linked list of arrays.
例如，虽然 XOR 链表每个项目花费 1 个指针，加上项目本身，但每个节点有 16 个项目的双向链表每 16 个项目花费 3 个指针，或每个项目 3/16 个指针.(额外的指针是记录节点中有多少项的整数的成本)它小于 1.在 Python 中有额外的开销，但它仍然工作得更好.
For example, while an XOR linked list costs 1 pointer per item, plus the item itself, A doubly-linked list with 16 items per node costs 3 pointers for each 16 items, or 3/16 pointers per item. (the extra pointer is the cost of the integer that records how many items are in the node) That is less than 1. In Python there are additional overheads, but it still works out better.
除了节省内存之外，您还可以获得局部性优势，因为节点中的所有 16 个项目在内存中彼此相邻.遍历列表的算法会更快.
In addition to the memory savings, you get advantages in locality because all 16 items in the node are next to each other in memory. Algorithms that iterate through the list will be faster.
请注意，XOR 链表还要求您在每次添加或删除节点时分配或释放内存，这是一项昂贵的操作.使用数组链表，您可以通过允许节点不完全满来做得比这更好.例如，如果您允许 5 个空项目槽，那么最坏情况下您只能在每 3 次插入或删除时分配或释放内存.
Note that an XOR-linked list also requires you to allocate or free memory each time you add or delete a node, and that is an expensive operation. With the array-linked list, you can do better than this by allowing nodes to be less than completely full. If you allow 5 empty item slots, for example, then you only have allocate or free memory on every 3rd insert or delete at worst.
这篇关于如何在 Python 中实现 XOR 链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
