如何在Cython中创建固定长度的可变Python对象数组?

Question

我需要一个包含Python对象的数组，用来创建一个前缀树（trie）数据结构。我想要一个固定长度的结构，像元组一样，同时又能像列表那样可变。我不想用列表，因为我希望能够确保这个列表的大小是完全正确的（如果它开始分配多余的元素，随着前缀树的增大，内存开销可能会迅速增加）。有没有什么方法可以做到这一点？我试着创建一个对象数组：

cdef class TrieNode:
    cdef object members[32]

...但是出现了错误：

Error compiling Cython file:
------------------------------------------------------------
...
cdef class TrieNode:
    cdef object members[32]
                      ^
------------------------------------------------------------

/Users/jason/src/pysistence/source/pysistence/trie.pyx:2:23: Array element cannot be a Python object

我该怎么做才能实现我的想法呢？

Answer 1

这个怎么样？

class TrieNode():
   def __init__(self, length = 32):
      self.members = list()
      self.length = length
      for i in range(length):
         self.members.append(None)

   def set(self, idx, item):
      if idx < self.length and idx >= 0:
         self.members[idx] = item
      else:
         print "ERROR: Specified index out of range."
         # Alternately, you could raise an IndexError.

   def unset(self, idx):
      if idx < self.length and idx >= 0:
         self.members[idx] = None
      else:
         raise IndexError("Specified index out of range (0..%d)." % self.length)

Answer 2

如果你只需要几个固定大小的这种结构，我建议你可以创建一些类，给它们统一命名的 __slots__，其中包括一个 size 的槽位来存储大小。你需要为每个大小（槽位的数量）声明一个单独的类。然后定义一个 cdecl 函数，通过索引来访问这些槽位。虽然这样访问的性能可能没有C语言数组那种直接的地址运算快，但你可以确保槽位的数量是有限的，不会多出一个。

Answer 3

我不知道什么是最好的解决方案，但这里有一个解决方案：

from cpython.ref cimport PyObject, Py_XINCREF, Py_XDECREF

DEF SIZE = 32

cdef class TrieNode:
    cdef PyObject *members[SIZE]

    def __cinit__(self):
        cdef object temp_object
        for i in range(SIZE):
            temp_object = int(i)
            # increment its refcount so it's not gc'd.
            # We hold a reference to the object and are responsible for
            # decref-ing it in __dealloc__.
            Py_XINCREF(<PyObject*>temp_object)
            self.members[i] = <PyObject*>temp_object

    def __init__(self):
        # just to show that it works...
        for i in range(SIZE):
            print <object>self.members[i]

    def __dealloc__(self):
        # make sure we decref the members elements.
        for i in range(SIZE):
            Py_XDECREF(self.members[i])
            self.members[i] = NULL

Cython中的object是一个自动管理引用计数的PyObject *。只要你愿意自己管理这些小家伙的引用计数，你总是可以自己创建PyObject *的数组。不过，对于一些复杂的情况，这可能会让人非常头疼。