cuda - 推力/cudpp中的算法找到第k个最小元素

Question

我正在寻找推力/cudapp 中第 k 个最小元素算法的实现。我用谷歌搜索了它，但似乎没有找到它。有谁知道是否存在这样的算法？

我看到有重新排序，但它没有说第 k 个最小。

Answer 1

Thrust 目前不提供选择算法（即std::nth_element在 STL 中），尽管它在我们的雷达上，并且有充分的证据表明可以在 GPU 上快速完成选择。您现在唯一的办法是使用thrust::sortor thrust::sort_by_key（或其stable_变体）对数据进行排序，然后选择适当的元素。在 Thrust 中对基本类型（例如int, float, char）double进行排序是使用非常快的基数排序代码实现的，因此绝对性能仍然相当不错，尽管不如专门的选择方法高效。