cythonのcdefクラスプロパティによる高速ソート

Question

2Dゲームエンジンでサポートされているスプライトの半透明性の一部として、フレームごとに行う必要があることの1つは、z_indexプロパティですべてのスプライトを並べ替えることです情報here）。次のように現在、私のcdef class RenderSystemに関連する骨格が見えます：

#lots of imports... 

cdef class RenderSystem: 

    def __init__(self): 
     #other irrelevant initialization stuff here 
     self.sprites = [] 

    def add_sprite(self, Sprite sprite): 
     self.sprites.append(sprite) 

    def remove_sprite(self, Sprite, sprite): 
     self.sprites.remove(sprite) 

    @cython.boundscheck(False) 
    @cython.wraparound(False) 
    @cython.initializedcheck(False) 
    @cython.cdivision(True) 
    @cython.infer_types(True) 
    @cython.binding(False) 
    def update(self): 
     self.sprites.sort(key=op.attrgetter("z_index"))#op = operator 
     #render-y OpenGL stuff goes here... 

基本的には、RenderSystemオブジェクトがcdef class Spriteオブジェクトののpython-隠されたリストを保持しています。ユーザーはこのリストから間接的にSpriteオブジェクトを追加または削除できます。私のSpriteクラスは、ユーザーが(-1.0, 1.0]の範囲で設定するcdef public float z_indexプロパティを持っています。 Spritez_indexの値を持つオブジェクトは、シーン内でより高い値のz_indexを持つオブジェクトの背後に表示されます。

sort機能だけでは、CPU使用量のかなりの部分（レンダリングなしで13％、レンダリングで> 25％（フルコア））が実現したことに気付きました。私はcythonで、代わりに（from libc.stdlib cimport qsort経由で）使用できるqsort c関数があることを知っています。しかし、qsorthereを読むと、それはのように見えます。それはfloat *z_index_listで渡されたものを注文し、Spriteオブジェクトとそのz_indicesの間の関連付けを失います。

TL; DR：cpythonの組み込みソート関数を実行できない特定の属性によってcdefクラスオブジェクトのリストをソートするための、いくつかの方法があります。

Answer 1

おそらく、属性アクセスをより効率的に（というよりも辞書の検索に頼る）することにより、中速アップを得ることができる：

def key_func(Sprite x): 
    return x.z_index 

または

def key_func(x): 
    return (<Sprite>x).z_index # this is an unsafe cast - you save time 
    # by avoiding type checking, but you're relying on it to be right 

---

私は」 dは、spritesを、cdefクラスのリストではなく、複雑なdtype（例：[('z_index', np.float_t), ...]）のnumpy配列にすることを強く検討します。これはPythonからアクセス可能で、Cythonを通じて効率的にアクセスできます。fast built-in sortを使用すると、注文に使用するフィールドを指定できます。