ビームサーチの上位 N件を高速に取る手法について考えてみる

ビームサーチでは候補となるノードを評価してその上位 N件を取得する処理が必要になるのですが、この部分をどう実装するのが高速なのかが度々話題になったりならなかったりします。 候補としては以下の 4つになります。(C++) sort nth_element partial_sort priority_queue 気になったので簡易的なコードを書いて実験してみました。（10万回ランダムに値を生成して、その中の値の小さい方から 100件を取得する。それを 1000回繰り返すコード） sort ver #include <algorithm> #include <iostream> #include <chrono> #include <vector> using namespace std; using namespace std::chrono; typedef long long ll; in