sorting - 双调排序网络 vs Thrust::sort_by_key

Question

我实现了一个使用排序的算法。我尝试了 Thrust::sort_by_key 大约需要 0.4 秒来对包含 10^7 个元素的数组进行排序。

我认为双音排序网络应该比 Thrust::sort_by_key 更快。但是，双调排序需要大约 2.5 秒才能对上述相同的数组进行排序。我使用了 SDK 提供的双音排序网络。我只是稍微修改了原来的双音排序。

你能告诉我为什么吗？或者给我一些建议？

谢谢，

易

2011 年 8 月 15 日

Answer 1

简短的回答是，CUDA SDK 提供的双音排序示例主要是为了教学。它根本不像 Thrust 的排序实现那样优化，后者基于Merrill提供的非常有效的基数排序。

两种算法的渐近性能也不同。双调排序网络具有O(n lg^2 n)复杂性，而 Thrust 采用的基数排序具有更类似于O(#bits n)复杂性的东西，其中#bits表示表示输入数据所需的位数。换句话说，基数排序比双调排序需要的全局内存读写次数渐进地少。

您可能会发现，对于较小的工作负载，双调排序表现更好。