8

我需要有一组 python 对象用于创建 trie 数据结构。我需要一个结构，它像元组一样是固定长度，像列表一样是可变的。我不想使用列表，因为我希望能够确保列表的大小完全正确（如果它开始分配额外的元素，那么随着 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

做我想做的事情的最佳方法是什么？

4

3 回答 3

5

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

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

Cythonobject是自动引用的PyObject *。PyObject *只要您负责重新计算小虫子，您就可以随时滚动自己的 's 数组。对于非平凡的案例来说，这可能是一个令人头疼的问题。

于 2011-02-17T19:25:21.460 回答
1

如果您只需要这种结构的几个固定大小，我会考虑制作具有统一命名的类__slots__，包括一个size用于存储大小的插槽。您需要为每个大小（插槽数）声明一个单独的类。定义一个cdecl按索引访问插槽的函数。访问性能可能不如 C 数组的普通地址算术那么好，但您会确定只有这么多插槽，没有更多。

于 2011-01-29T01:40:52.517 回答
0

这个怎么样？

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)
于 2011-01-28T23:56:24.887 回答