推力stable_sort_by_key O(n)？

Question

我可以假设在unsigned int上执行的推力unsigned int具有复杂性O(n)吗？如果不是，我应该怎么做才能确保这一复杂性得到实现？(除了我自己实现基排序之外)

Answer 1

这在一定程度上取决于你的情况/观点。仅仅从docs/API来看，使用基排序似乎不能保证thrust::stable_sort_by_key上的unsigned int键。

另一方面，必要的算法cub::DeviceRadixSort::SortPairs是在后台Thrust使用的CUB库中实现的，没有充分的理由不使用它，因为编译时可以很容易地查询先决条件。

从thrust/system/cuda/detail/sort.h中的代码( "detail“应该警告您这不是公共API的一部分)可以看到，thrust::stable_sort_by_key可以在正确的情况下(算术键类型并使用thrust::less或thrust::greater作为比较操作)启动cub::DeviceRadixSort::SortPairs，至少可以在撰写本报告时的主要推力分支 (大约2.0.0rc2)上启动，但可能已经有很长时间了。否则，它将返回到合并排序。

直接使用cub::DeviceRadixSort::SortPairs可能有好处，即使这对您来说已经足够了，因为这样可以更容易地重用临时缓冲区并避免不必要的同步。这两种方法都可以通过

auto exec = thrust::cuda::par_nosync(custom_allocator).on(custom_stream);

执行策略(最新的CUDA工具包11.8仍然有旧的推力v1.15没有v1.16 par_nosync)。使用推力不能避免的一件事是排序算法的就地性质，这是通过将结果复制回输入缓冲区来实现的。这些复制操作只能使用CUB来省略。