如何比快速排序更快地排序整数数组？

  • Z时代
  • 2024-01-10
  • 分类：问答

使用numpy的quicksort对整数数组进行排序已成为我算法的瓶颈。不幸的是，numpy还没有

基数排序。尽管计数排序在numpy中是一线的：

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

回答：

不，您不会被quicksort所困扰。你可以使用，例如， integer_sort从

Boost.Sort

或u4_sort从usort。排序此数组时：

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

我得到以下结果：

NumPy快速排序：8.636 s 1.0（基准）
Boost.Sort integer_sort：4.327 s 2.0x加速
usort u4_sort：2.065 s 4.2倍加速

我不会单凭实验得出结论，也不会usort盲目使用 。我会用我的实际数据进行测试并衡量会发生什么。您的里程

根据您的数据和机器而有所不同。该 integer_sort在Boost.Sort拥有一套丰富的用于调节选项，请参阅

文档。

下面，我描述了两种从Python调用本机C或C ++函数的方法。尽管描述很长，但是这样做很容易。

将这些行放入spreadsort.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_sort为32位无符号整数实例化模板。该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以下命令将C

++函数包装在Python中：

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包装函数。

至于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文件所在的目录中发出此命令。（可能没有那么多hacker的方法，但是我没有弄清楚。我只是查看了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包装函数即可。

以上是 如何比快速排序更快地排序整数数组？ 的全部内容， 来源链接： utcz.com/qa/409456.html

回到顶部