c++ - std::nth_element 的 SIMD 实现

Question

我有一个算法可以在我的双核 3 GHz Intel 处理器上平均运行 250 毫秒，我正在尝试优化它。目前，我有一个 std::nth_element在 std::vector 上调用了大约 6,000 次的调用s 在 150 到 300 个元素之间，平均耗时 50 毫秒。我花了一些时间优化我使用的比较器，它目前查找两个 double s 来自 vector 并执行简单的 <比较。比较器运行时间的一小部分可以忽略不计 std::nth_element .比较器的复制构造函数也很简单。

因为这个调用目前占用了我算法 20% 的时间，而且大部分时间花在了 nth_element 的代码上。我没有写(即不是比较器)，我想知道是否有人知道优化 nth_element 的方法使用 SIMD 或任何其他方法？我看过some questions关于并行化 std::nth_element使用 OpenCL 和多线程，但由于 vector 非常短，我不确定我能从这种方法中获得多少好处，尽管我愿意被告知我错了。

如果有 SSE 方法，我可以使用任何 SSE 指令(我认为是当前的)SSE4.2。

谢谢!

Answer 1

两个想法:

1. 多线程可能不会加快任何单个 vector 的处理速度，但可能会随着 vector 数量的增加而有所帮助。

2. 排序对于解决您的问题来说是一个太强大的工具:您正在计算 vector 的整个顺序，但您只关心前几个。对于每个 vector ，您知道有多少元素构成了前 5%，因此您应该让 一个 遍历数组并找到最大的 k 而不是对整个事物进行排序。您可以用 O(n) 的时间和 k 的额外空间完成此操作，因此这可能是总体上的胜利。