numpy 数组的并行就地排序

Question

我经常需要对大型numpy数组(几十亿个元素(进行排序，这成为我代码的瓶颈。我正在寻找一种并行化它的方法。

ndarray.sort()函数是否有任何并行实现？numexpr 模块为 numpy 数组上的大多数数学运算提供了并行实现，但缺乏排序功能。

也许，可以围绕并行排序的C++实现制作一个简单的包装器，并通过 Cython 使用它？

Answer 1

我最终包装了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(链接(

此生成文件将执行此操作：

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]

编辑：修复了下面评论中注意到的错误

Answer 2

Mergesort非常自然地并行化。只需让每个工作线程预先排序一个任意块，然后对其运行单个合并传递。最终的合并应该只需要 O(N( 操作，并且在 numba 或类似的东西中编写一个函数是微不足道的。

维基百科同意