SIMD实现std :: nth_element

Question

我有一个算法,运行在我的双核,3 GHz英特尔处理器平均250毫秒,我正在尝试优化它.目前,我有一个std::nth_element呼叫,std::vector在150到300个元素之间调用大约6000次,平均需要50ms.我花了一些时间来优化我使用的比较器,它目前double从向量中查找两个并执行简单的<比较.比较器运行的时间可以忽略不计std::nth_element.比较器的拷贝构造函数也很简单.

由于此调用当前占用了我的算法的20%的时间,并且由于时间大部分花费在nth_element我没写的代码上(即不是比较器),我想知道是否有人知道优化的方法nth_element使用SIMD或任何其他方法？我已经看到了一些关于std::nth_element使用OpenCL和多线程进行并行化的问题,但由于这些向量很短,我不确定从这种方法中获得多少好处,尽管我很容易被告知我错了.

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

谢谢!

Answer 1

两个想法：

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

2. 对于您的问题来说，排序是一个太强大的工具：您正在计算向量的整个顺序，但除了前几个之外，您不关心任何东西。您知道每个向量有多少个元素构成前 5%，因此您应该遍历数组并找到最大的元素，而不是对整个元素进行排序k。你可以O(n)用k额外的空间来做到这一点，所以这可能是总体上的胜利。