How to create a fixed size, resizable array of Python objects in Cython?

Question

I need to have an array of python objects that will be used when creating the trie data structure. I need a structure that will be a fixed length as a tuple and modified as a list. I don’t want to use the list because I want to be able to make sure that the list matches the size exactly (if it starts to allocate additional elements, the memory overhead can add up very quickly as the trie gets bigger). Is there any way to do this? I tried to create an array of objects:

cdef class TrieNode: cdef object members[32] 

... but this gave an error:

 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 

What is the best way to do what I'm trying to do?

Answer 1

I don't know about a better solution, but here is a solution:

 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 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 

A Cython object is an automatically recalculated PyObject * . You can always collapse your own PyObject * arrays while you take responsibility for recounting the little crawlers. This can be a major headache for non-trivial cases.

Answer 2

If you only need a few fixed sizes of such a structure, I would look at classes with the uniformly named __slots__ , including one size slot for storing the size. You will need to declare a separate class for each size (number of slots). Define a cdecl function to access slots by index. Access performance will probably not be as large as with simple arithmetic of C array addresses, but you will be sure that there will only be so many slots and no more.

Answer 3

How about this?

 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)