SIMD std :: nth_element的實現

我有一種算法可以在我的雙核3 GHz Intel處理器上平均運行250ms，並且我正在優化它。目前，我有一個std::nth_element調用，在150到300個元素的std::vector之間調用約6000次，平均需要50ms。我花了一些時間來優化我使用的比較器，它目前從向量中查找兩個double，並進行簡單的<比較。比較器運行時間可以忽略不計，可運行std::nth_element。比較器的複製構造器也很簡單。SIMD std :: nth_element的實現

由於此調用目前佔用了我算法的20％時間，並且由於時間主要用於我沒有編寫的代碼nth_element（即不是比較器），所以我想知道是否有人知道使用SIMD或其他方法優化nth_element的方法？我已經看到some questions使用OpenCL和多線程並行化std::nth_element，但由於向量很短，我不確定從這種方法得到多少好處，儘管我很樂於被告知我錯了。

如果有證的做法，我可以使用任何SSE指令最多（目前，我認爲）SSE4.2。

謝謝！

來源

2013-11-22 anjruu

你可以發佈一些代碼？你想優化什麼？ –

@BЈовић我可以發佈_something_，但我不確定它會是多麼有用。我有幾千行代碼，我試圖優化所有的代碼。這是一個視覺算法。你想看見什麼？ – anjruu

是的，我們在這裏需要更多的上下文。你有一堆小小的雙打矢量，你正在嘗試對它們進行排序嗎？你的最終目標是什麼？ –

兩個想法：

多線程可能不會對任何單一載體加快處理速度，但作爲載體的數量變大可能會幫助你。
排序是太強大了你的問題的工具：你計算的矢量的整個訂單，但你不關心，除了前幾名。你知道每個矢量有多少元素組成了前5％，所以不應該整理整個東西，而應該讓一個通過陣列並找到最大的k。你可以做到這一點，O(n)與k額外的空間，所以它可能是一個整體的勝利。

來源

2013-11-22 15:23:24

SIMD std :: nth_element的實現

回答

相關問題