为什么不能在python3中建立一个异或链表？

Question

我想在 python 中实现一个 xor 链表，我搜索它试图更好地理解它，但我发现的唯一与 python 相关的是这个 Whosebug post How to implement an XOR Linked List in Python? 表示不可能在 python 中实现异或链表。它在那里说你不能乱用位和指针。我认为我们实际上可以 'mess with bits'，使用按位运算符（对于 xor 我们会有 ^ ），指针是什么意思？我们可以创建一个带有指针属性的节点 class，就像我们在单链表中所做的那样：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

那将是我们的节点 'pointer' -> .next。所以，问题是，为什么我们不能在 python 中实现 XOR 链表，如果可以，怎么做？

Answer 1

异或链表存储两个地址的异或以节省存储空间space。这在直接操作内存地址的低级语言中很有用。在 Python 中没有那么多，因为在 Python 中你不直接处理内存。

Python 名称（变量）是对 Python 运行时管理的对象的引用。 但该引用不是内存地址。

在 CPython 中，您可以 或多或少 使用 id() 函数获取对象的地址，但这是一个 CPython 的实现细节，而不是语言的属性。此外，Python 对象比您想象的要大得多。在类 C 语言中，一个整数通常是 4 个字节。

Python 为“有效的数值数组”提供了 array。让我们创建一个 4 字节整数数组；

In [5]: import array

In [6]: a = array.array('l', range(10))
Out[6]: array('l', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

让我们看看数组中第一项和第二项的地址之间的差异：

In [7]: id(a[1]) - id(a[0])
Out[7]: 32

所以在我的机器上，作为 CPython 对象的 4 字节整数 的大小实际上是 32 字节。这基本上是因为 Python 运行时必须在幕后做很多工作来为您管理内存。

Answer 2

我可以成功实现异或链表。请注意，为了设置 Node 的邻居，您必须传递这两个邻居。如果不这样做，则无法使用 XOR 运算计算地址 (address_store = prev_address ^ curr_address)。

get_by_address(address) 函数将在运行时为您提供给定 id 的对象，而 Node.get_address(node) 将为您提供 Node 的 id。显然，可以取消引用 Python 中的一个对象并获得它的引用！

def get_by_address(address, global_vars):
    if address == 0:
        return None

    return [x for x in global_vars.values() if id(x) == address][0]

class Node(object):
    def __init__(self, data):
        self.data = data
        self.address_store = None

    def get_address(self):
        return id(self)

    def set_neighbors(self, prev_node=None, next_node=None):
        local_address = self.get_address()

        if prev_node == None:
            prev_address = 0
        else:
            prev_address = prev_node.get_address()

        if next_node == None:
            next_address = 0
        else:
            next_address = next_node.get_address()

        self.address_store = prev_address ^ next_address

    def get_next(self, prev_node, global_vars):
        if self.address_store == None:
            raise Exception('set_neighbors not called yet, no next node!')

        if prev_node == None:
            prev_address = 0
        else:
            prev_address = prev_node.get_address()

        next_address = self.address_store ^ prev_address

        return get_by_address(address=next_address, global_vars=global_vars)

    def get_prev(self, next_node, global_vars):
        if self.address_store == None:
            raise Exception('set_neighbors not called yet, no next node!')

        if next_node == None:
            next_address = 0
        else:
            next_address = next_node.get_address()

        prev_address = self.address_store ^ next_address

        return get_by_address(prev_address, global_vars=global_vars)

node1 = Node(data=1)
node2 = Node(data=2)
node3 = Node(data=3)

node1.set_neighbors(prev_node=None, next_node=node2)
node2.set_neighbors(prev_node=node1, next_node=node3)
node3.set_neighbors(prev_node=node2, next_node=None)

curr_node = node1
prev_node = None

print('Traversing forwards:')

print(str(None), '<->', end=' ')

while curr_node != None:
    print(curr_node.data, '<->', end=' '),

    prev_node_temp = curr_node
    curr_node = curr_node.get_next(prev_node=prev_node, global_vars=globals())
    prev_node = prev_node_temp

print(str(None))

curr_node = node3
prev_node = None

print('Traversing backwards:')

print(str(None), '<->', end=' ')

while curr_node != None:
    print(curr_node.data, '<->', end=' '),

    prev_node_temp = curr_node
    curr_node = curr_node.get_next(prev_node=prev_node, global_vars=globals())
    prev_node = prev_node_temp

print(str(None))

输出：

Traversing forwards:
None <-> 1 <-> 2 <-> 3 <-> None
Traversing backwards:
None <-> 3 <-> 2 <-> 1 <-> None

为什么不能在python3中建立一个异或链表？

Why can't you build a xor linked list in python 3?

python

algorithm

bit-manipulation

xor-linkedlist