Понимание использования модуля ctypes в этом примере кода - PullRequest
Новая
       32

Понимание использования модуля ctypes в этом примере кода

0 голосов
/ 24 ноября 2018

Контекст: Некоторый код, который я нашел, который реализует связанный список XOR.В связанном списке XOR вместо каждого узла, имеющего следующий указатель, он имеет атрибут both, который представляет собой XOR предыдущего и следующего узла. 

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

Вопросы:

  1. Не понимаете, зачем нужна функция _get_obj() и что она пытается здесь делать?
  2. Чем полезен self.__nodes = []?И как здесь реализована сборка мусора?

  3. Понятия не имею, что делает следующий код: 

    # Without this line, Python thinks there is no way to reach nodes between
# head and tail.
self.__nodes.append(node)`

1 Ответ

0 голосов
/ 24 ноября 2018

Я могу ответить на большинство подвопросов в вашем вопросе.

  1. функция _get_obj() является собственной id() обратной функцией Python (синтерпретатор CPython в любом случае).Есть и другие способы сделать это.См., Например, вопрос Можно ли разыменовать идентификатор переменной? .

  2. & 3. self.__nodes.append(node) добавляет экземпляр Node в частный список, посколькудобавление его в связанный список XOR не создает ссылку на него, как это могло бы случиться в более обычной нормальной реализации (трюк XOR устраняет необходимость в них).Без этого сборщик мусора Python может удалить экземпляр Node, пока он все еще был частью связанного списка.

...