Параллельный вид на месте для массивов numpy

Question

Мне часто приходится сортировать большие массивы numpy (несколько миллиардов элементов), что стало узким местом моего кода. Я ищу способ распараллеливать его.

Существуют ли параллельные реализации для функции ndarray.sort()? Модуль Numexpr обеспечивает параллельную реализацию для большинства математических операций на массивах numpy, но не имеет возможностей сортировки.

Возможно, возможно создать простую оболочку вокруг реализации параллельной сортировки на C++ и использовать ее через Cython?

Answer 1

Mergesort распараллеливается вполне естественно. Просто каждый работник предварительно сортирует произвольный кусок, а затем запускает на нем один проход слияния. Окончательное слияние должно требовать только O (N) операций, и его тривиально написать функцию для этого в numba или somesuch.

Wikipedia agrees

Answer 2

я в конечном итоге упаковки GCC параллельной сортировки. Вот код:

parallelSort.pyx

# cython: wraparound = False 
# cython: boundscheck = False 
import numpy as np 
cimport numpy as np 
import cython 
cimport cython 

ctypedef fused real: 
    cython.char 
    cython.uchar 
    cython.short 
    cython.ushort 
    cython.int 
    cython.uint 
    cython.long 
    cython.ulong 
    cython.longlong 
    cython.ulonglong 
    cython.float 
    cython.double 

cdef extern from "<parallel/algorithm>" namespace "__gnu_parallel": 
    cdef void sort[T](T first, T last) nogil 

def numpyParallelSort(real[:] a): 
    "In-place parallel sort for numpy types" 
    sort(&a[0], &a[a.shape[0]]) 

Дополнительные аргументы компилятора: -fopenmp (компиляции) и -lgomp (связь)

Это Makefile будет делать это:

all: 
    cython --cplus parallelSort.pyx 
    g++ -g -march=native -Ofast -fpic -c parallelSort.cpp -o parallelSort.o -fopenmp `python-config --includes` 
    g++ -g -march=native -Ofast -shared -o parallelSort.so parallelSort.o `python-config --libs` -lgomp 

clean: 
    rm -f parallelSort.cpp *.o *.so 

И это показывает, что оно работает:

from parallelSort import numpyParallelSort 
import numpy as np 
a = np.random.random(100000000) 

numpyParallelSort(a) 
print a[:10] 

Редактировать: исправлена ​​ошибка, отмеченная в комментарии ниже