Sort memoryview in Cython

Question

How can I sort a memoryview in-place in Cython? Is there a built-in function that can do it? Right now I have to use a numpy array instead and use numpy's sort, which is very slow.

Ambrose

Is the issue with the performance of numpy.sort or with the cost of copying the memoryview to a numpy array? If it's the latter then np.asarray(memview) should work without the copy. – Tigges

@Tigges It's a problem with the performance of numpy.sort – Ambrose

You could trying telling numpy to use a different algorithm (I think it has a choice of 3). If that doesn't help you could use the C++ standard library cplusplus.com/reference/algorithm/sort. You can use it with pointers so it'd be something like sort(&memview[0],&memview[length]) (note that you pass it one element past the end. You'd need to compile it with C++ though. – Tigges

Answer 1

To follow up on my comment, here are 3 options (numpy and a C and C++ standard library option)

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 you'll will depend on which C/C++ standard library you're using so don't read too much into my results. For a 1000 long array (sorted 5000 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 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

i.e if you're sorting lots of small arrays, the overhead of calling numpy sort is large and you should use C++ (or possibly C). If you're sorting large arrays you may find it hard to beat numpy.

Tigges

Perfect, thanks. The overhead of calling numpy was causing problems for me – Ambrose

This answer should be updated. The sort_c doesn't work. Change double to int and use array([ 2, 20, 6, 5, 22, 17, 13, 7, 2, 8], dtype=int32), got array([22, 20, 6, 13, 2, 2, 7, 8, 17, 5], dtype=int32). – Deanadeanda

@Deanadeanda It works for me. Did you remember to change cmp_func to be int too? – Tigges

Yes. Strange to me too. I tried the example in Kurt W. Smith's book Cython, it worked, but this one doesn't. – Deanadeanda

@Deanadeanda I really don't know - as I say it works for me in both int and double forms. It's fairly simple so I really can't see anywhere for it to be wrong. I think that's probably the limit of my interest in looking back at this answer – Tigges