如何比quicksort更快地对整数数组进行排序？

Question

用numpy的快速排序对整数数组进行排序已经成为我算法的瓶颈.不幸的是,numpy还没有 基数排序.虽然计算排序将是numpy中的单行:

np.repeat(np.arange(1+x.max()), np.bincount(x))

看到我如何对这个python计数排序进行矢量化的接受答案,以便它绝对尽可能快？问题,我的应用程序中的整数可以运行0到2**32.

我坚持使用quicksort吗？

---

_{这篇文章的主要动机是使用itertools.groupby性能 问题进行 Numpy分组.
另请注意, 提出并回答您自己的问题不仅可以,而且明确鼓励.}

Answer 1

不,你不会被快速排序困住.你可以使用,例如, integer_sort从 Boost.Sort 或u4_sort从usort.排序此数组时:

array(randint(0, high=1<<32, size=10**8), uint32)

我得到以下结果:

NumPy quicksort:         8.636 s  1.0  (baseline)
Boost.Sort integer_sort: 4.327 s  2.0x speedup
usort u4_sort:           2.065 s  4.2x speedup

我不会根据这个单一的实验得出结论并usort盲目地使用 .我会测试我的实际数据并测量会发生什么.您的里程将根据您的数据和您的机器而有所不同.该 integer_sort在Boost.Sort拥有一套丰富的用于调节选项,请参阅 文档.

下面我将介绍两种从Python调用本机C或C++函数的方法.尽管有很长的描述,但它很容易实现.

Boost.Sort

将这些行放入spreadort.cpp文件中:

#include <cinttypes>
#include "boost/sort/spreadsort/spreadsort.hpp"
using namespace boost::sort::spreadsort;

extern "C" {
    void spreadsort(std::uint32_t* begin,  std::size_t len) {
        integer_sort(begin, begin + len);
    }
}

它基本上实例化integer_sort32位无符号整数的模板; 该extern "C"部分通过禁用名称修改来确保C链接.假设您正在使用gcc并且必需的boost文件位于/tmp/boost_1_60_0目录下,您可以编译它:

g++ -O3 -std=c++11 -march=native -DNDEBUG -shared -fPIC -I/tmp/boost_1_60_0 spreadsort.cpp -o spreadsort.so  

关键标志是-fPIC生成 位置独立代码 并-shared生成 共享对象 .so文件.(阅读gcc的文档以获取更多详细信息.)

然后,spreadsort()使用ctypes以下命令在Python中包装C++函数:

from ctypes import cdll, c_size_t, c_uint32
from numpy import uint32
from numpy.ctypeslib import ndpointer

__all__ = ['integer_sort']

# In spreadsort.cpp: void spreadsort(std::uint32_t* begin,  std::size_t len)
lib = cdll.LoadLibrary('./spreadsort.so')
sort = lib.spreadsort
sort.restype = None
sort.argtypes = [ndpointer(c_uint32, flags='C_CONTIGUOUS'), c_size_t]

def integer_sort(arr):
    assert arr.dtype == uint32, 'Expected uint32, got {}'.format(arr.dtype)
    sort(arr, arr.size)

或者,您可以使用cffi:

from cffi import FFI
from numpy import uint32

__all__ = ['integer_sort']

ffi = FFI()
ffi.cdef('void spreadsort(uint32_t* begin,  size_t len);')
C = ffi.dlopen('./spreadsort.so')

def integer_sort(arr):
    assert arr.dtype == uint32, 'Expected uint32, got {}'.format(arr.dtype)
    begin = ffi.cast('uint32_t*', arr.ctypes.data)
    C.spreadsort(begin, arr.size)

在cdll.LoadLibrary()和ffi.dlopen()调用我假设spreadsort.so文件的路径是./spreadsort.so.或者,你可以写

lib = cdll.LoadLibrary('spreadsort.so')

要么

C = ffi.dlopen('spreadsort.so')

如果将路径追加spreadsort.so到LD_LIBRARY_PATH环境变量.另请参见共享库.

用法.在这两种情况下,您只需integer_sort() 使用32位无符号整数的numpy数组调用上面的Python包装函数.

usort

至于u4_sort,您可以按如下方式编译它:

cc -DBUILDING_u4_sort -I/usr/include -I./ -I../ -I../../ -I../../../ -I../../../../ -std=c99 -fgnu89-inline -O3 -g -fPIC -shared -march=native u4_sort.c -o u4_sort.so

在u4_sort.c文件所在的目录中发出此命令.(可能有一种不那么强硬的方式,但我没有想到这一点.我只是查看了usort目录中的deps.mk文件,找出必要的编译器标志并包含路径.)

然后,您可以按如下方式包装C函数:

from cffi import FFI
from numpy import uint32

__all__ = ['integer_sort']

ffi = FFI()
ffi.cdef('void u4_sort(unsigned* a, const long sz);')
C = ffi.dlopen('u4_sort.so')

def integer_sort(arr):
    assert arr.dtype == uint32, 'Expected uint32, got {}'.format(arr.dtype)
    begin = ffi.cast('unsigned*', arr.ctypes.data)
    C.u4_sort(begin, arr.size)

在上面的代码中,我假设路径u4_sort.so已经附加到LD_LIBRARY_PATH环境变量.

用法.和之前的Boost.Sort一样,您只需integer_sort()使用32位无符号整数的numpy数组调用上面的Python包装函数.