SIMD実装のstd :: nth_element

Question

平均250msで私のデュアルコア、3 GHz Intelプロセッサで動作するアルゴリズムがあり、それを最適化しようとしています。現在、std::nth_elementコールは、std::vectorで約6,000回呼び出され、150〜300要素の平均50msを要します。私は現在、ベクトルから2つのdoubleを検索し、単純な<の比較を行う、私が使用するコンパレータを最適化するのに少し時間を費やしました。コンパレータは、実行する時間のほんのわずかです。std::nth_element。コンパレータのコピーコンストラクタもシンプルです。

このコールは現在アルゴリズムの時間の20％を費やしているので、私が書き込んでいない（つまりコンパレータではない）nth_elementのコードではほとんど時間が費やされているので、誰かが知っていればSIMDまたは他の方法を使用してnth_elementを最適化する方法を教えてください。私は、OpenCLと複数のスレッドを使用してstd::nth_elementを並列化することでsome questionsを見たことがありますが、ベクトルがかなり短いので、私は間違っていると言われていますが、

SSEアプローチがある場合は、SSE4.2までのSSE命令を使用することができます。

ありがとうございます！

Answer 1

つの思考：

1. マルチスレッドは、おそらく任意の単一のベクトルの処理をスピードアップしませんが、ベクトルの数が多くなるにつれて、あなたを助けるかもしれません。

2. 並べ替えは、あなたの問題のためには非常に強力なツールです。ベクターの全体の順序を計算していますが、上位のものだけは気にしません。各ベクトルについて、上位5％を構成する要素の数を知っているので、全体をソートする代わりに、をの1つにして、kを最大にする必要があります。これはO(n)時にはk余分なスペースがあるので、おそらく全体的に勝利でしょう。