Почему вы не можете создать связанный список xor в python 3? - PullRequest
Новая
       23

Почему вы не можете создать связанный список xor в python 3?

1 голос
/ 26 апреля 2020

Я хотел реализовать связанный список xor в python, и я искал его, чтобы попытаться понять его лучше, но единственная вещь, связанная с python, которую я нашел, была в этом сообщении stackoverflow Как реализовать связанный XOR Список в Python? , который говорит, что невозможно реализовать связанный список xor в python. Там сказано, что вы не можете связываться с битами и указателями. Я думаю, что мы можем на самом деле «связываться с битами», используя побитовые операторы (для xor у нас будет ^) и что это означает под указателями? Мы можем создать класс узла со свойством указателя, как мы делали бы в односвязном списке: 

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

И это был бы наш узел с указателем -> .next. Итак, вопрос в том, почему мы не можем реализовать связанный список XOR в python, и если мы можем, то как?

Ответы [ 2 ]

2 голосов
/ 26 апреля 2020

Я мог бы успешно реализовать связанный список XOR. Обратите внимание, что для установки соседей 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
1 голос
/ 26 апреля 2020

Связанный список xor хранит xor двух адресов для экономии места на диске. Это может быть полезно в низкоуровневых языках, которые напрямую манипулируют адресами памяти. В Python не так много, потому что в Python вы не обрабатываете память напрямую.

Python Имена (переменные) являются ссылками на объекты, управляемые средой выполнения Python. Но эта ссылка не является адресом памяти.

В CPython вы можете больше или меньше получить адрес объекта с помощью id() функция, но это деталь реализации из CPython, а не свойство языка. Кроме того, Python объекты намного больше, чем вы думаете. В C -подобных языках целое число обычно составляет 4 байта.

Python предоставляет array для "эффективных массивов числовых значений c. Давайте создадим массив из 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

Итак, на моей машине размер 4-байтового целого числа как CPython объект на самом деле составляет 32 байта. Это в основном потому, что среда выполнения Python должна выполнять большую работу за кулисами, чтобы управлять памятью для вас.

...