Idiom: Partial Sorting - agwの日記

書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::partial_sortを使ったほうが効率的であるようです。

std::vector<int> a;

// ...aを更新する

std::partial_sort(std::begin(a),
                  std::begin(a) + 20,
                  std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

イテレータを3つ取る関数には苦手意識がありましたが、この用法は覚えやすいですし、手軽な定数倍高速化として重宝するかもしれません。計算量は面白く、

$$ O({}(\mathrm{last} - \mathrm{first})\log(\mathrm{middle} - \mathrm{first}){}) $$

だそうです。線形の項が配列全体の要素数なので劇的に計算量が減るわけではなさそうですが、以下のように一定の効果は期待できそうです。

$$ \begin{array}{cccc} \mathrm{first} & \mathrm{middle} & \mathrm{last} & \text{Complexity}\\ \hline 0 & 10 & 1000 & 1000 \times 3.322\\ 0 & 100 & 1000 & 1000 \times 6.644\\ 0 & 500 & 1000 & 1000 \times 8.966\\ 0 & 1000 & 1000 & 1000 \times 9.966\\ \end{array} $$

よしよし、一つ賢くなったぞ...と喜んでいたのも束の間、合計を取りたいのであればstd::nth_elementで十分であることに気づきました。std::nth_elementはstd::partial_sortと書式がほとんど一緒ですが、std::partial_sortが先頭から20要素までに上位20個の要素を整列して格納するのに比べ、先頭から20要素までに上位20個の要素を格納する、とのこと。

std::vector<int> a;

// ...aを更新する

std::nth_element(std::begin(a),
                 std::begin(a) + 20,
                 std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

(この用途では¹)計算量はstd::parital_sortに比べとても効率的で、$O(\mathrm{last} - \mathrm{first})$だそうです。$\log$が落ちてしまうんですね。