Sorting memory in Cython

Question

How can I sort memory in place in Cython? Is there a built-in function that can do this? Now I have to use a numpy array and use numpy sort, which is very slow.

Answer 1

To follow my comment, here are 3 options (numpy and the standard C and C ++ library)

 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) 

The results will depend on which standard C / C ++ library you use, so do not read too much in my results. For a 1000 long array (sorted 5,000 times) I get:

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

i.e. The numpy version is the fastest. For a 100 long array, I get

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

If you are sorting a large number of small arrays, the overhead of calling numpy sort calls is high and you should use C ++ (or maybe C). If you are sorting large arrays, it may seem difficult to beat numpy.