早まった最適化

B003LMJGUY日経ソフトウエア 2010年 07月号を見ていたら、こんな記事がありました。

このプログラムを速くせよ!(p.114)

問2

int isPrimeNumber(int n) {
  int i, ans;

  ans = -1;
  for (i = 2; i <= (int) sqrt(n); i++) {
    if (n % i == 0) {
      ans = 0;
      break;
    }
  }
  return ans;
}

解答は想像通りのものでしたが、本当にそういう修正が必要なのかどうかは、(規格はともかく)私たちがコンパイラに何を求めるかによると思います。

コンパイラが、「errnoのチェックはしてないみたいですね。じゃあ、for文の評価でsqrtを何度も呼ぶのはやめましょう」と勝手に判断して、gccのオプション「-fno-math-errno」に相当する最適化をすることを私は期待します。

などということを考えさせるいい問題です。実は、素数だったら-1を返すという仕様のほうが気になるのですが、結果を数字と比較するわけではないのでまあいいでしょう。

問3も同じ感じですね。

問4のような関数を学生が書いてきたら、解答例のように書き直すのではなく、Lispを紹介ししたくなります。

4874084141問5の解答は、「よい子はまねをしないでね」というやつですね。高速化云々よりも、2次方程式を題材にして、数値アルゴリズムを紹介した本(例:奥村晴彦『C言語による最新アルゴリズム事典』)にはたいてい載っているような、誤差を少なくするための工夫をあえてしないところがにくいです。

問6も同様で、どうやって速くするかよりも、「(a+ b) / 2」を「a / 2 + b / 2」にすることをまず考えさせる良問です。

「早まった最適化は諸悪の根源だ」とまでは言いませんが、「最適化の前にやるべきことがある」ということは体験できるでしょう。

このほかにも、日経ソフトウェア7月号には、勉強になりそうな記事がいろいろありそうです。

特集「PHP5とSymfony1.4で作るTwitterアプリ」で紹介されているTwitterアプリは、6/30を過ぎたら動かくなるという厳しいタイマーが付いています。7月号でそれはちょっと厳しいんじゃないかと思いますが、動くように修正するのは、よいトレーニングになるでしょう。

「再入門!いまどきのJavaScript」ではGoogle Maps API バージョン2を使っています。1年くらい前に出たバージョン3ではなく、あえてバージョン2を使うあたりが教育的です。バージョン3を使おうと思ったら、自分で、ネットで、英語で勉強しなければならないわけですが、これもまたよいトレーニングになるでしょう。