通過cython中的cdef class屬性快速排序

作爲支持2D遊戲引擎中精靈半透明的一部分，我需要做的每一幀的事情之一就是將z_index屬性從後到前排序爲所有的精靈（更多info here）。目前，我cdef class RenderSystem相關骨架如下所示：通過cython中的cdef class屬性快速排序

#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對象的蟒蛇隱藏列表。用戶然後可以間接地從這個列表添加或刪除對象。我的Sprite類具有cdef public float z_index屬性，用戶在(-1.0, 1.0]範圍內設置屬性。 Sprite將較低的對象z_index的值呈現在場景中具有較高值z_index的值後面。我意識到單獨使用sort函數佔用了我CPU佔用量的很大一部分（13％沒有渲染，> 25％（一個完整核心）渲染）。我知道在cython中，我們有一個qsort c函數可以用來代替（通過from libc.stdlib cimport qsort）。然而，閱讀qsorthere，它看起來像qsort只會命令通過float *z_index_list，我會失去Sprite對象和它們的z_indices之間的關聯。

TL; DR：在cython中，通過給定的屬性對cdef類對象列表進行排序可以超出cpython的內置排序函數的其他更快的方法是什麼？

來源

2017-07-18 CodeSurgeon

你也許可以得到通過使屬性的訪問更加高效（而不是依靠一個字典查找）中等加速：

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成爲一個具有複雜dtype的數組（例如[('z_index', np.float_t), ...]）而不是cdef類的列表。這可以通過Python訪問，可以通過Cython高效訪問，並且有一個fast built-in sort，它允許您指定用於訂購的字段。

來源

2017-07-18 06:52:49 DavidW

謝謝你一如既往！使用'key_func'可以省掉一些CPU％（現在9％不渲染，大約與渲染相同的25％）。我會嘗試重構代碼來使用numpy。如果我走的是顛簸路線，這是否允許我保持我的'Sprite'類不變？儘管我的Sprite類有很多數值屬性和固定大小的浮點數組，但它也依賴於一個與OpenGL顯着交互的Texture類。我正在考慮在numpy數組中存儲指向這些對象的uint32_t指針（'Sprite'對象及其子''Texture'）來解決這個問題... – CodeSurgeon

如果你存儲指向其他Python/Cython類的指針，那麼numpy數組可能不是一個好的解決方案。 – DavidW

不管怎麼說，只是出於好奇而嘗試過numpy，是的，排序性能與您的'key_func'大致相同，除了添加和（尤其是）刪除精靈速度很慢（不是太奇怪，因爲數組是固定大小的，我需要刪除元素在中間，並在末尾添加一個新元素以避免數組中的「洞」）。還有其他建議嗎？ – CodeSurgeon

通過cython中的cdef class屬性快速排序

回答

相關問題