Cython "Память, эффективная с двойной связью" - PullRequest
Новая
       11

Cython "Память, эффективная с двойной связью"

0 голосов
/ 17 октября 2019

В качестве упражнения я собираю двусвязный список, используя XOR для указателей, чтобы упростить необходимость хранить только одно значение на узел. Я пытаюсь использовать Cython, который является новым для меня, и я быстро разработал следующий шаблон, не зная, будут ли функции Cython работать должным образом 

cdef class Node:
    def __init__(self, object val, void* prev_xor_next=NULL):
        self.prev_xor_next=prev_xor_next
        self.val=val

    def __repr__(self):
        return str(self.val)

cdef class CurrentNode(Node):
    def __init__(self, Node node, void* prev_ptr=NULL):
        self.node=node
        self.prev_ptr=prev_ptr

    cpdef CurrentNode forward(self):
        if self.node.prev_xor_next:
            return CurrentNode((self.node.prev_xor_next^self.prev_ptr)[0], &self.node)

    cpdef CurrentNode backward(self):
        if self.prev_ptr:
            return CurrentNode(self.prev_ptr[0], (&self.node)^(self.prev_ptr[0]).prev_xor_next)

cdef class XORList:
    cdef Node first, last, current

    cpdef append(self, object val):
        if not first:
            self.first=CurrentNode(Node(val))
            self.last=self.first
            self.current=self.first
        else:
            if last==first:
                self.last=CurrentNode(Node(val))
                self.first.node.prev_xor_next=(&self.last.node)^self.first.prev_ptr
                self.first=self.first.node
                self.last.prev_ptr=&self.first
            else:
                temp=CurrentNode(Node(val))
                self.last.node.prev_xor_next=(&self.temp.node)^self.last.prev_ptr
                self.temp.prev_ptr=&self.last
                self.last=temp

    cpdef reverse(self):
        temp=self.last
        self.last=self.first
        self.first=temp

    def __iter__(self):
        return self

    def __next__(self):
        if not self.current or not self.current.forward():
            self.current=CurrentNode(self.first)
            raise StopIteration()
        ret = self.current
        self.current=self.current.forward()
        return ret

    def __repr__(self):
        cdef str ret =''
        for i in self:
            ret+='<=>'+str(i)
        return ret

Проблемы, с которыми я столкнулся, включают получение указателей натипы расширений и передача указателей на конструкторы. Второй вариант, который я нашел, решен с помощью статического фабричного метода, но я оставил это здесь, чтобы, надеюсь, сохранить шаблон, который я пытаюсь прояснить.

Я уже пытался заменить Node структуройиз-за этого я не могу принять объект python в качестве значения узла.

Я изучил PyObject и PyCapsule, но мне тоже не повезло с ними, что может быть просто из-за отсутствия пониманияих использование, хотя их базовые цели кажутся ясными.

Есть ли подход, который позволяет использовать этот шаблон с использованием Cython?

Пожалуйста, прости любые логические ошибки в коде. Я не проверял это, и это просто упражнение.

1 Ответ

2 голосов
/ 18 октября 2019

Вы можете приводить типы расширений к указателям и от них, используя синтаксис приведения к угловым скобкам. Часто стоит использовать тип PyObject*, который вы можете cimport from cpython.object, однако вы также можете перейти непосредственно к void*: 

from cpython.object cimport PyObject

cdef Node n = Node()
cdef PyObject* nptr1 = <PyObject*>n
cdef void* nptr2 = <void*>n
cdef void* nptr3 = <void*>nptr1

Чтобы вернуться к типу cdef: 

cdef Node new_node = <Node>nptr1

Единственное, что не разрешит вам Cython: 

# ERROR: Storing unsafe C derivative of temporary Python reference
cdef PyObject* bad = <PyObject*>Node()

Он понимает, что новый Node перестанет существовать почти сразу после его создания, поэтому указатель мгновенно становится недействительным. В отличие от них nptr1, nptr2 и nptr3 действительны, по крайней мере, до тех пор, пока n не переназначен.

Обратите внимание, что вы должны сами обрабатывать подсчет ссылок,Вы можете снова получить доступ к соответствующей функции с помощью cimport: from cpython.ref cimport Py_XINCREF, Py_XDECREF. Функции берут PyObject*, поэтому полезно его использовать. Если вы намереваетесь сохранить один из этих указателей, вам нужно увеличить счетчик ссылок, и вам следует уменьшить счетчик ссылок, когда вы закончите с ним.

Я не знаю точно, какой счетчик ссылок должен бытьсделано для вашего xor-ed списка, но вам нужно будет это сделать !

Здесь также потенциально может быть более тонкая проблема подсчета ссылок: если у вас есть циклические ссылки (например, если Node содержит ссылку на XOrList), тогда она никогда не будет освобождена. Cython пытается создать функции, которые обрабатывают циклические ссылки для классов cdef, однако он не понимает (и не может) понять, что вы делаете с указателями, поэтому они будут исключены;это не легко переопределить это поведение.

...