条件チェックの順の最適化 - Pixel Pedals of Tomakomai

複数の条件をすべて満たすときだけ、処理を継続したいということはよくあると思う。例えば以下のようなコード。

fn some_function(x: &Hoge) {
    if !check0(x) {
        return;
    }
    if !check1(x) {
        return;
    }
    if !check2(x) {
        return;
    }
    if !check3(x) {
        return;
    }
    
    // x に対する処理
}

このとき、 check0 から check3 をどのような順番でチェックするのが一番効率がいいだろう？直感的には、一番通りにくいチェックを最初にやっておいたほうが、残りの処理をスキップできて効率がいいように思える。しかし、それぞれのチェックにある程度時間がかかってしまうときにはどうだろうか？

例えば、処理するデータのうち各チェックが NG となる割合と、チェックに要する時間が以下の表のとおりだったとする。例えばチェック3は、6割のデータがブロックされて以降の処理をスキップできるが、チェックするのに 5 msec もかかってしまう。どの順番に並べるのがいいだろうか？

	NGの割合	所要時間(msec)
check0	0.2	1
check1	0.3	2
check2	0.4	4
check3	0.6	5

答えから言うと、所要時間÷NGの割合の昇順で並べると一番効率が良い。この例だと、 check0 check1 check3 check2 の順番にチェックするのが最適となる。

理由を簡単に説明する。 $check_i$ について、 NG の割合を $p_i$ 、所要時間(cost) を $c_i$ とする。まず、チェックが $check_0$ ～ $check_n$ まで並んでいるときに、ある $i$ について $\frac{c_i}{p_i} \gt \frac{c_{i + 1}}{p_{i+1}}$ が成立するとする。このとき、 $check_i$ と $check_{i + 1}$ を入れ替えると、コストの期待値が下がることを示すことができる。

実際、 $i + 2$ 以降のチェックにかかるコストの期待値を $D$ とすると、 $check_i$ 以降の処理でかかるコストの期待値は $c_i + (1 - p_i)(c_{i+1} + (1 - p_{i + 1})D)$ となる。 $check_i$ と $check_{i + 1}$ を並び替えた場合のコストを引き算をして整理すると、 $p_{i + 1}p_i(\frac{c_i}{p_i} - \frac{c_{i + 1}}{p_{i + 1}})$ という式が得られ、最初の仮定からこの式は正の値を取る。よって、並び替える前のほうがコストが高いことが言え、すなわち目標としていた事実が示された。

後は任意のチェックの列があった場合に、連続する 2 つの「チェックの所要時間÷NGの割合」の値が昇順になっていない部分を入れ替え続けることでどんどんコストを下げることができ、最終的には列全体がこの値の昇順となったときにコストは最小になる、ということである。

今回の check0 ～ check3 について、実際にシミュレーションするコードを github に上げておいた。

https://github.com/hiratara/rs-error-check-optimization-simulation/blob/026792790836c04829040fa9a7a346ff74eec10d/src/main.rs

このシミュレーションを実行すると、以下の出力が得られ、実際に並び替えることで性能が向上していることがわかる(元々最適解に近い並び方なので、ほんとにちょっとだけ)。ちなみに、逆の順で並べてしまうのが最悪ケースで、かなりパフォーマンスが悪化することもわかる。

$ ./target/release/rs-error-check-optimization-simulation
68.68248 sec
optimized order: [0, 1, 3, 2]
66.66192 sec (optimized)
worst order: [2, 3, 1, 0]
78.78843 sec (worst)

ちなみに、今回は関数の呼び出し時間の文脈で考えたが、製品の各検査における不具合率とかかる金額（コスト）の文脈でも同じ考え方になるだろう。