2

cython で一般的な並べ替えアルゴリズムを実装しようとしています。そこで、クラス内に Heapsort アルゴリズムを実装する次のモジュールを作成しましたsorter_t

# file general_sort_c.pyx

from libc.stdint cimport int32_t
cdef bint bint_true = 1
cdef bint bint_false = 0

cdef class sorter_t:

    cdef object sortable_object

    def __init__(self,sortable_object):
        self.sortable_object = sortable_object

    cpdef sort_c(self):

        """
        https://en.wikipedia.org/wiki/Heapsort

        """

        cdef int32_t end
        cdef int32_t count = self.sortable_object.num_elements_int32

        self.heapify_c(count)

        end = count-1 
        while end > 0:
            self.sortable_object.swap_c(0,end)
            end = end - 1
            self.siftDown_c(0,end)

    cdef heapify_c(self,int32_t count):

        cdef int32_t start = (count - 2)/2   

        while start >= 0:
            self.siftDown_c(start, count-1)
            start -= 1

    cdef siftDown_c(self,int32_t start, int32_t end):

        cdef int32_t root = start
        cdef int32_t swap
        cdef int32_t child

        while root * 2 + 1 <= end:

            child = root * 2 + 1 
            swap = root

            # if "swap" < "child" then ...
            if self.sortable_object.lt_c(swap,child) == 1:
                swap = child

            if child+1 <= end and self.sortable_object.lt_c(swap,child+1) == 1:
                swap = child + 1

            if swap != root:
                self.sortable_object.swap_c(root,swap)
                root = swap
            else:
                return

型のオブジェクトを定義するときは、cdef 関数(ある要素が他の要素よりも小さいかどうかを比較するため) および(要素を交換するため)の独自の特定の実装を持つ をsorter_t提供する必要があります。sortable_objectlt_cswap_c

たとえば、次のコードはsortable_objectリストから を定義および作成し、それを使用して「sorter_t」の実装をテストしsortable_objectます。

import numpy
cimport numpy
from libc.stdint cimport int32_t
import general_sort_c

cdef class sortable_t:

    cdef public int32_t num_elements_int32
    cdef int32_t [:] mv_lista

    def __init__(self,int32_t [:] mv_lista):
        self.num_elements_int32 = mv_lista.shape[0]
        self.mv_lista = mv_lista

    cdef public bint lt_c(self, int32_t left, int32_t right):
        if self.mv_lista[left] < self.mv_lista[right]:
            return 1 # True
        else:
            return 0 # False

    cdef public bint gt_c(self, int32_t left, int32_t right):
        if self.mv_lista[left] > self.mv_lista[right]:
            return 1 # True
        else:
            return 0 # False

    cdef public swap_c(self, int32_t left, int32_t right):
        cdef int32_t tmp
        tmp = self.mv_lista[right]
        self.mv_lista[right] = self.mv_lista[left]
        self.mv_lista[left] = tmp

def probar():

    lista = numpy.array([3,4,1,7],dtype=numpy.int32)
    cdef int32_t [:] mv_lista = lista

    cdef sortable = sortable_t(mv_lista)
    cdef sorter = general_sort_c.sorter_t(sortable)
    sorter.sort_increasing_c()
    print list(lista)

両方のファイルをコンパイル.pyxし、IPython コンソールで次のコマンドを実行すると、次のエラーが発生します。

In [1]: import test_general_sort_c as tgs

In [2]: tgs.probar()      

...

 general_sort_c.sorter_t.siftDown_increasing_c (general_sort_c.c:1452)()
    132 
    133             #if mv_tnet_time[swap] < mv_tnet_time[child]:

--> 134             if self.sortable_object.lt_c(swap,child) == bint_true:
    135                 swap = child
    136 

AttributeError: 'test_general_sort_c.sortable_t' object has no attribute 'lt_c'

したがって、問題は、関数の実装がlt_cmodule のコードから見えないことですgeneral_sort_c.pyx。代わりにlt_c使用して関数を定義すると機能しますが、Python のオーバーヘッドが大きくなります。この関数を(「純粋な C」) 方法で呼び出す方法は?cpdefcdefcdef

4

1 に答える 1

1

残念ながら、これを融合型で機能させる方法はわかりませんが、残りは非常に簡単です。

test_general_sort_c.pyx無料が必要test_general_sort_c.pxdです :

from libc.stdint cimport int32_t

cdef class sortable_t:
    cdef public int32_t num_elements_int32
    cdef int32_t [:] mv_lista
    cdef public bint lt_c(self, int32_t left, int32_t right)
    cdef public bint gt_c(self, int32_t left, int32_t right)
    cdef public swap_c(self, int32_t left, int32_t right)

general_sort_c.pyx次に、それを acimport test_general_sort_cと入力する必要があります。self.sortable_objecttest_general_sort_c.sortable_t

もちろん、サポートされているタイプが多数ある場合は、これがはるかに優れています。しかし、今のところあなたがそれをどのように行うかはわかりません。


また、ビルトインTrueFalse、それ自体で正常に動作します。

Cython をもう少し信頼していれば、次のように書けることに気付くでしょう。

cdef public bint lt_c(self, int32_t left, int32_t right):
    return self.mv_lista[left] < self.mv_lista[right]

cdef public bint gt_c(self, int32_t left, int32_t right):
    return self.mv_lista[left] > self.mv_lista[right]

cdef public swap_c(self, int32_t left, int32_t right):
    self.mv_lista[right], self.mv_lista[left] = self.mv_lista[left], self.mv_lista[right]

大丈夫です。:)

于 2013-09-20T19:07:04.923 に答える