在Cython中对memoryview进行排序

Question

我该如何在Cython中就地对memoryview进行排序？ 有没有内置的函数可以做到这一点？目前，我不得不使用numpy数组，并使用numpy的排序，这非常慢。

- C_Z_

---

numpy.sort 的性能问题是出在哪里，还是由于将 memoryview 复制到 numpy 数组的成本过高？如果是后者，那么 np.asarray(memview) 应该可以避免复制。 - DavidW

@DavidW 这是numpy.sort性能的问题。 - C_Z_

你可以尝试告诉NumPy使用不同的算法（我觉得有3种选择）。如果这样做没有帮助，你可以使用C++标准库http://www.cplusplus.com/reference/algorithm/sort/。你可以用指针来使用它，就像是 sort(&memview[0],&memview[length])（注意你要传递的是结尾元素的下一个位置）。不过你需要使用C++编译。 - DavidW

Answer 1

针对我的评论，这里有三个选项（numpy和C、C++标准库选项）。

from libcpp.algorithm cimport sort
from libc.stdlib cimport qsort

import numpy as np

def sort_numpy(double[:] a, kind):
    np.asarray(a).sort(kind=kind)

# needs to be compiled with C++        
def sort_cpp(double[::1] a):
    # a must be c continuous (enforced with [::1])
    sort(&a[0], (&a[0]) + a.shape[0])

# The C version requires a comparator function
# which is a little slower since it requires calling function pointers
# and passing pointers rather than numbers
cdef int cmp_func(const void* a, const void* b) nogil:
    cdef double a_v = (<double*>a)[0]
    cdef double b_v = (<double*>b)[0]
    if a_v < b_v:
        return -1
    elif a_v == b_v:
        return 0
    else:
        return 1

def sort_c(double[:] a):
    # a needn't be C continuous because strides helps
    qsort(&a[0], a.shape[0], a.strides[0], &cmp_func)

你所得到的结果将取决于你使用的 C/C++ 标准库，因此不要过分解读我的结果。对于一个长度为 1000 的数组（排序了 5000 次），我得到的结果如下：

np quick:  0.11296762199890509
np merge:  0.20624926299933577
np heap:  0.2944786230000318
c++:  0.12071316699984891
c:  0.33728832399901876

即numpy版本最快。对于长度为100的数组，我得到

np quick:  0.022608489000049303
np merge:  0.023513408999860985
np heap:  0.024136934998750803
c++:  0.008449130998997134
c:  0.01909676999821386

即，如果您要对许多小数组进行排序，则调用numpy sort的开销很大，因此应使用C++（或可能是C）。 如果您要对大型数组进行排序，您可能会发现很难超越numpy。

- DavidW

---

完美，谢谢。调用Numpy的开销对我造成了问题。 - C_Z_

这个答案需要更新。sort_c 不起作用。将 double 改为 int 并使用 array([ 2, 20, 6, 5, 22, 17, 13, 7, 2, 8], dtype=int32)，得到 array([22, 20, 6, 13, 2, 2, 7, 8, 17, 5], dtype=int32)。 - Elkan

@Elkan，这对我有效。你记得把cmp_func也改成int了吗？ - DavidW

是的，这对我来说也很奇怪。我尝试了 Kurt W. Smith 的书《Cython》中的示例，它可以工作，但这个却不行。 - Elkan

@Elkan 我真的不知道 - 就像我说的，它在 int 和 double 形式下都对我有效。它相当简单，所以我真的看不出哪里有错。我想这可能是我回顾这个答案兴趣的极限了。 - DavidW