上下文:
我发现一些代码实现了异或链表。在异或链表中,不是每个节点都有一个下一个指针,而是有一个 both
属性,该属性是前一个节点和下一个节点的异或。
import ctypes
# This is hacky. It's a data structure for C, not python.
class Node(object):
def __init__(self, val):
self.val = val
self.both = 0
class XorLinkedList(object):
def __init__(self):
self.head = self.tail = None
self.__nodes = [] # This is to prevent garbage collection
def add(self, node):
if self.head is None:
self.head = self.tail = node
else:
self.tail.both = id(node) ^ self.tail.both
node.both = id(self.tail)
self.tail = node
# Without this line, Python thinks there is no way to reach nodes between
# head and tail.
self.__nodes.append(node)
def get(self, index):
prev_id = 0
node = self.head
for i in range(index):
next_id = prev_id ^ node.both
if next_id:
prev_id = id(node)
node = _get_obj(next_id)
else:
raise IndexError('Linked list index out of range')
return node
def _get_obj(id):
return ctypes.cast(id, ctypes.py_object).value
问题:
- 不明白
_get_obj()
函数的必要性及其尝试的用途 在这里做什么? self.__nodes = []
有什么用处?以及它是如何实现的 这里有垃圾收集吗?我不知道以下代码在做什么:
# Without this line, Python thinks there is no way to reach nodes between # head and tail. self.__nodes.append(node)`
最佳答案
我可以回答您问题中的大部分子问题。
_get_obj()
函数是 Python 自己的逆函数id()
函数(无论如何使用 CPython 解释器)。 还有其他方法可以做到这一点。例如,参见问题 Is it possible to dereference variable id's? .& 3.
self.__nodes.append(node)
将Node
实例添加到私有(private)列表,因为将其添加到 XOR 链表不会不要创建对它的引用,就像在更常见的正常实现中可能发生的那样(异或技巧消除了对它们的需要)。如果没有这个,Python 垃圾收集器可能会删除仍然是链接列表一部分的Node
实例。
关于python - 了解此示例代码中 ctypes 模块的用法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53455560/