11

多くの場合、大きなでこぼこの配列 (数十億要素) をソートする必要があり、これがコードのボトルネックになりました。並列化する方法を探しています。

関数の並列実装はありndarray.sort()ますか? Numexpr モジュールは、numpy 配列に対するほとんどの数学演算の並列実装を提供しますが、並べ替え機能がありません。

おそらく、並列ソートの C++ 実装の周りに単純なラッパーを作成し、それを Cython で使用することは可能でしょうか?

4

2 に答える 2

9

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]

編集：以下のコメントで指摘されたバグを修正

于 2015-02-22T21:18:17.877 に答える
2

Mergesort は非常に自然に並列化します。各ワーカーに任意のチャンクを事前に並べ替えさせてから、単一のマージ パスを実行するだけです。最終的なマージには O(N) 操作のみが必要であり、それを行うための関数を numba などで記述するのは簡単です。

ウィキペディアは同意します

于 2014-12-27T10:40:34.940 に答える