我有一个算法可以在我的双核 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。
谢谢!
最佳答案
两个想法:
多线程可能不会加快任何单个 vector 的处理速度,但可能会随着 vector 数量的增加而有所帮助。
排序对于解决您的问题来说是一个太强大的工具:您正在计算 vector 的整个顺序,但您只关心前几个。对于每个 vector ,您知道有多少元素构成了前 5%,因此您应该让 一个 遍历数组并找到最大的
k
而不是对整个事物进行排序。您可以用O(n)
的时间和k
的额外空间完成此操作,因此这可能是总体上的胜利。
关于c++ - std::nth_element 的 SIMD 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20147665/