C Magazine の最後に載っていたパズルを楽しみにされていた方には当たり前のことですが、繰り返し処理をする場合、繰り返さなければならない条件をあらかじめ限定してしまうと、実行スピードが飛躍的に向上します。
例として、1～1000 の範囲で、素数を求めてみます。
素数は、1以上の整数で、1とその数以外に割り切ることのできる数がない数字です。具体的に列挙すると、2, 3, 5, 7, 11, 13, 17, 19, ... という感じ。
こいつを安直に求めるなら、こんな風になります。
2～1000 までのループをする（変数Ｎ）
割り切れたフラグ = false
2～(Ｎ-1)までのループをする（変数Ｍ）
ＮをＭで割り、余りを求める
あまりがなければ割り切れたフラグを true にして、ブレーク
変数Ｍのループ
割り切れたフラグが false なら、Ｎを印字する
変数Ｎのループ
さて、これの、どこが無駄なのでしょうか？
変数Ｎのループですが、2 以外の“偶数”は、必ず 2 で割れるので、素数ではないことがわかりきっています。そのため、4 以降の偶数をループするのが無駄。Ｍのループについても、2 で割り切れなかったということは、他の偶数でも割り切れるはずがありません。従って、Ｍのループも1つ飛ばしにできます。
数学的に詳しい人なら、Ｍのループ回数をさらに減らせるでしょう。
"2" を印字する
3～1000 までのループをする（変数Ｎ、増分 2）
割り切れたフラグ = false
3～(Ｎ-1)までのループをする（変数Ｍ、増分 2）
ＮをＭで割り、余りを求める
あまりがなければ割り切れたフラグを true にして、ブレーク
変数Ｍのループ
割り切れたフラグが false なら、Ｎを印字する
変数Ｎのループ
単純に考えます。ＮもＭもループする回数が半分になっているので、下のコードでだと、上のコードの１／４の時間で実行が完了することが見込めます。製造時にちょっと悩むことによって、実行時の時間が１／４になる。すばらしいことだと思いませんか？
もちろん、微々たる実行時間が短縮することと、製造時間をかけることのバランスを気にする人もいるでしょう。
しかし。ソフトウェア提供者が提供するのは、単なるソフトウェアなのでしょうか？
あるいは、同じことができる機械、たとえばミュージック プレイヤーを購入するとき、同じような機能なのに iPod が売れている理由は何でしょう？
同じことができるのであるなら、より使いやすい、よりわかりやすいものを選ぶのではないでしょうか。では、同じ「素数を求める」プログラムで、実行時間が 4秒のものと 1秒のものがあるなら、1秒のものを選ぶのではないでしょうか。
製造工程を大幅に修正する必要なく、ちょっと気の利いたことができるなら、それを実装することを“付加価値”とする意味は、あるのではないでしょうか。
タイトルを「条件を刈り込む」としましたが、「設計しましょう」をテーマにお送りしました。
追加：επιστημηさんとえムナウさんのコメントより。
Ｍのループについて考えます。このループは、Ｎで割りきれる数を探すものです。36で考えます。
36を素因数分解すると、36 ÷ 2 → 18 ÷ 2 → 9 ÷ 3 → 3 で、2, 2, 3, 3 です。ここから、36になるかけ算の組み合わせを列挙します。
| 2 |
2 × 3 × 3 |
2 × 18 |
| 3 |
2 × 2 × 3 |
3 × 12 |
| 2 × 2 |
3 × 3 |
4 × 9 |
| 2 × 3 |
2 × 3 |
6 × 6 |
| 3 × 3 |
2 × 2 |
9 × 4 |
| 2 × 2 × 3 |
3 |
12 × 3 |
| 2 × 3 × 3 |
2 |
18 × 2 |
こうすると、4行目、6 × 6 の上下で、かけ算の右と左の数字が入れ替わるだけということがわかります。かけ算は、順番が入れ替わっても答えは同じですから、この場合は4行目までの計算をすれば、全組み合わせを検査したことになります。
では、4行目をどのようにして求めましょう？素因数を見ると、左右が同じ数字です。つまり、Ｎの平方根（√Ｎ）です。
投稿日時 : 2007年3月19日 22:12