品質とひきかえに犠牲になるもの

1. 電子さいころプログラム

あるプロジェクトのソースプログラムを見る必要に迫られて見ていたところ、 とんでもない書き方をしているところがあった。 やりたいことは、1から100までの数字を無作為に（ランダムに）５個選ぶことである。 ５個の順番も無作為である（小さい順とか、大きい順ではない）。 さあ、どうするか。 1から100までの乱数（ランダムな数）を発生するサブルーチンは使えるものとする。 サブルーチンということばがわからなければ、 1から100まで100種類の目がある電子さいころとでも思って下さればいい。

2. 素朴な考え

これを、ふつうに、素朴に考えたらどうするだろう。ふつうは次のように考えるだろう。

1. １個めは、サブルーチンを走らせて数(aとする)を決める。
2. ２個めは、aでない数字(bとする)が出るまでサブルーチンを走らせる。
3. ３個めは、aでもbでもない数字(cとする)が出るまで、サブルーチンを走らせる。
4. ４個めは、aでもbでもcでもない数字(dとする)が出るまで、サブルーチンを走らせる。
5. ５個めは、aでもbでもcでもdでもない数字(eとする)が出るまで、サブルーチンを走らせる。

これは、正しい答えを出す。しかし、なんとなく野暮な感じがする。 下手をすれば何度もサブルーチンを走らせてしまう（サイコロをふってしまう）ようだ。 この方法を使う時、サブルーチンを走らせる回数（サイコロをふる回数）を求めるのは もっとかっこいい方法はないだろうか。

3. 数が小さい順に出てもいいのなら

選ぶ５個の数値が小さい順でよいなら、こんな方法がある。m = 5, n = 100　とする。

1. k=1とする。
2. 確率 m/n で k を出力する。
3. 2.でkを出力したらm = m-1, n = n-1, とする。
4. 2.でkを出力しなければn = n-1 とする。
5. k が 5 回出力されたならば終わり。 そうでなければk = k+1とし、2.へもどる。

なんのことかわからないだろう。この手続きがうまくいく理由を説明することは少し難しい。

4. さらにいろいろ

サブルーチンの呼び出し回数を少なくするとか、選ぶ５個の数値の大小の順もランダムにしたいとか、 いろいろなことが考えられる。そうして、それぞれ対応した考え方（アルゴリズム）は存在する。 たとえば、呼び出し回数についていえば、選ぶ回数だけで答えが決まるアルゴリズムはある。

わたしは最初、とんでもない書き方をしているプログラム、といった。 それは、一番最初に紹介した素朴なプログラムである。 今は100個から5個を選んでいるが、 このどちらも変わった時、特に選ぶ個数が変わった時の拡張性がない。 また、サブルーチンは呼ばれる回数が少なければ少ないほどいい。

ところが、とんでもない書き方で一点だけいいことがある。 それは「何をやっているかわかる」のである。 「数が小さい順に出てもいいのなら」で紹介した方法は、なぜそれでうまくいくのか、 という問いに答えようとすると時間がかかる。すなわち、 高校の確率ぐらいの知識と理解力が必要になる。 それに比べば、素朴な書き方は考えている通りにプログラムを書いているだけのことである。 何かプログラムに問題があったとしても、 それを見る人にとってわかりやすいという利点はある。

つまり、計算の主要品質である効率性を追求するあまり、 別の主要品質である保守性が損なわれることもありうる、 というのがいいたいことである。ただし、今挙げた程度の例では、 保守性を損なうほどの複雑さはない。

もっともいいのは、よいアルゴリズムを使い、なおかつ説明を十分行うことである。 よいアルゴリズムが紹介されている参考文献を掲げる。

1. ベントレー：プログラマのうちあけ話（近代科学社）
2. 奥村晴彦：C言語による最新アルゴリズム辞典（技術評論社）

ベントレーの本はアルゴリズムのみが示されている（コラム１３）。 奥村の本には、 ベントレーの本で示されたアルゴリズムをC言語に翻訳した例が示されている。 ただし順序のランダム性については無視している。

5. 犠牲になるもう一つのもの

実はこのページの制作と並行して、 JavaScript により上記アルゴリズムを実装していた。 その過程はランダム順列というページに記した。 なんと、私はバグのあるアルゴリズムを公開してしまったのだ。 つまり、実装も難しい、ということになる。 これの対策は、一つはテストをきちんと行う、ということだろう。 それから、関数の特性を正しく把握する、というのも反省点である。 (この項、2010-05-16 追加)

まりんきょ学問所 ＞ 品質の部屋 ＞ 品質とひきかえに犠牲になるもの