Parallele In-Place-Sortierung für numpy Arrays

Question

Ich muss oft große numpy Arrays (einige Milliarden Elemente) sortieren, was zu einem Engpass in meinem Code wurde. Ich suche nach einer Möglichkeit, es parallel zu machen.

Gibt es parallele Implementierungen für die ndarray.sort() Funktion? Das Numexpr-Modul bietet eine parallele Implementierung für die meisten mathematischen Operationen auf numpigen Arrays, aber es fehlen Sortiermöglichkeiten.

Vielleicht ist es möglich, einen einfachen Wrapper rund um eine C++ - Implementierung der parallelen Sortierung zu erstellen, und verwenden Sie es über Cython?

Answer 1

Mergesort parallelisiert ganz natürlich. Lassen Sie jeden Worker einen beliebigen Chunk vorsortieren, und führen Sie dann einen einzigen Merge-Durchlauf für ihn aus. Das endgültige Zusammenführen sollte nur O (N) -Operationen erfordern, und es ist trivial, eine Funktion dafür in Numba oder dergleichen zu schreiben.

Wikipedia agrees

Answer 2

Ich landete GCC parallele Sortierung Verpackung. Hier ist der Code:

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]]) 

Extra-Compiler argumente: -fopenmp (kompiliert) und -lgomp (Verknüpfung)

Diese Make-Datei wird es tun:

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 

Und das zeigt, dass es funktioniert:

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

numpyParallelSort(a) 
print a[:10] 

edit: behobener Fehler im Kommentar bemerkt