PR

 プログラミングの作業の中で,最もプログラミングらしく,最も楽しい作業といったら何といってもアルゴリズム(algorithm,算法)の組み立てだろう。難しい機能を実現するために,ああでもないこうでもないと思慮を巡らすのは楽しいものだ。うまいアルゴリズムが思い付いたりすれば,幸せな気分になれる(と,思うのは筆者だけだろうか)。

1000以下の素数を求めるプログラム?

 例えば,1000以下の素数(1とその数以外では割り切れない自然数。2,3,7や59など)を求めるプログラムを作れと言われたら,どのような構造のプログラムを考えるだろうか?

 すぐに予想できるのは,1から1000までの値nについて,nが素数かどうかを順番に判定するというものだろう。素数かどうかの判定は,nが2から(n-1)までの値で割り切れるかどうかを調べればよい。どの値でも割り切れなければ素数ということになる。これで出来上がりだ。

 しかし,よく考えてみるとこのプログラムは効率が悪い。最初に一つ割り切れる値が見つかった時点で素数でないことはわかるので,2から(n-1)までの値で割り切れるかどうかをすべてチェックする必要がないからだ。

 また,2で割り切れないことがわかったら,4(2×2)や8(2の3乗)…といった2の乗数でも割り切れないことがわかる。さらに3でも割り切れなければ,2×3や2a×3bでも割り切れないので,これらの値のチェックを省略できる。つまり,すでにわかっている素数で割り切れるかどうかだけをチェックすればよいことになる。nがcで割り切れて,答えがdになるなら,dで割れるかを調べる必要はない。つまり,nの平方根より小さい値までを調べればよいことになる。しかも偶数は素数でないので,奇数だけ調べればよい。――以上から,(1)3以上の奇数,(2)nの平方根より小さい素数で割り切れるかどうかを調べるアルゴリズムが良さそうである。

 最初の総当りによる方法だと99万9000回も割り算をチェックしなくてはならなかったが,改良した方法では1804回(2と3は素数なので,次の素数5から調べる)になる。平方根の計算や条件判断が増えるので,除算の数だけをみて速度向上できるとは一概には言えないが,大幅に処理効率が向上するのは確実だ。このように良いアルゴリズムを使うと,プログラムの中の無駄を削ぎ落とすことができ,大幅な効率の改善が望める。

 だからといって,すべてのプログラムに対して,自分でゼロからアルゴリズムを考え出すというのは大変な作業である。最高のアルゴリズムを思い付ける保証は何もない。

 そこで先人の知恵,すなわちアルゴリズムの解説書が必要になってくる。アルゴリズムの解説書には,有名なアルゴリズムの紹介だけでなく,どのようにしてアルゴリズムを考え出すかということや,考え出したアルゴリズムをどのように評価するか,といったことが書かれている。新しいアルゴリズムを思い付いたときの評価の物差しも手に入れられるというわけだ。

やさしく読める入門書で頭を鍛えよう

 最初に紹介するのは,アルゴリズムの入門書である。基本的にアルゴリズムは「考え方」なので,プログラミング言語の種類とは関係ないが,実装して考えるときにはプログラムを書く必要がある。したがって,まったく知識のないプログラミング言語を題材にして書かれたアルゴリズム解説本は避けた方がよい。とはいえ,条件分岐,ループ,演算子,変数の宣言について理解できれば,たいていの本は読めるはずだ。

図解入門
よくわかる
アルゴリズム
の基本と仕組み

杉浦 賢 著
秀和システム 発行
2002年3月
255ページ
C言語による
アルゴリズムと
データ構造

柴田 望洋,辻 亮介 著
ソフトバンク
パブリッシング 発行
2002年7月
325ページ+CD-ROM

 例えば,プログラミング言語を勉強中で,並行してアルゴリズムも勉強しようと考えているなら「図解入門 よくわかるアルゴリズムの基本と仕組み」がお薦めである。この本では,C言語を使ってアルゴリズムのプログラミングを説明しているが,フローチャートを使った説明だけでほぼすべて理解できる。Cのコードは「アルゴリズムをプログラミングするとこうなる」という例に過ぎない。コードをまったく読まなくても,アルゴリズムを理解できるはずだ。

 第3章までは準備なので,さっと流して読んでもよいだろう。第4章から,探索,並べ替え,再帰,積分の近似といった,一般的なアルゴリズムの説明が始まる。最終部分ではアルゴリズムの評価法もあるので,アルゴリズムで何を注意すべきかイメージするには十分な内容だ。

 ただし,それぞれのアルゴリズムについての深い説明がなく,一つの問題に対して複数のアルゴリズムを試していないので,深くアルゴリズムを知りたいという人には物足りない。逆に言えばさらっと読める内容なので,アルゴリズムにちょっと興味があるという人が入門の第一歩として気軽に手にとるにはとても良い。

 では,ある程度C言語を使っている人に向く本はないのか。それなら「C言語によるアルゴリズムとデータ構造」がいいだろう。この本はアルゴリズムの説明だけでなく,C言語を使ったプログラミングについても触れている。また,「C言語によるプログラミングはこうあるべき」という筆者の考えが,ところどころに表れている。これは,C言語やC++の解説書を多く執筆している柴田望洋氏が筆者の一人として加わっているためかもしれない。

 内容としては,アルゴリズムの基本から説明を始め,データ型,探索,再帰,並べ替え,文字列処理,木構造などの説明を盛り込んでいる。コードを紹介しながら多くの図を使って説明してあるので,比較的簡単に理解できる。付録CD-ROMには,アルゴリズム体験ソフトや情報処理技術者試験の過去問題と解説,さらにはC言語の入門書まで入っている。一つの問題をさまざまなアルゴリズムで考察したりと内容は深い。半面,さらっと読むのにはつらい。パソコンに向かって自分で試しながら読むのに適している。

数学好きのためのアルゴリズム本

改訂 C言語による
はじめての
アルゴリズム入門

河西 朝雄 著
技術評論社 発行
2001年7月
483ページ+CD-ROM

 次に紹介するのは「改訂 C言語によるはじめてのアルゴリズム入門」である。この本は少し数学の素養を必要とするが,それさえクリアできれば,非常にわかりやすく,多くの種類のアルゴリズムを勉強できる。

 「ウォーミングアップ」と題された最初の章で,パスカルの三角形,モンテカルロ法による円周率の求め方,ユークリッドの互除法,前述した素数の求め方(このページで説明した方法と少し違う)などがスピーディに掲載されている。この章がほとんど理解できない場合は,正直,あまりお薦めできない。しかし,概略は理解できるというレベル以上ならば,続く内容も理解できるだろう。

 非常に豊富なアルゴリズムをぎっしりつめこんであり,「こういうときにうまいアルゴリズムがあったかな?」というときに何らかのヒントを見付けられる。しかし,個々のアルゴリズムに対する説明はあまり詳しくない。特に数値計算のアルゴリズムの説明では,多くの数式が書かれ,その解き方についての説明も少ない。正直,数学の教科書がないと読むのはつらい。難解な数式は出てこないが,数学が苦手の人には難しいかもしれない。

 説明しているアルゴリズムは,先に挙げた2冊の内容に加え,数値計算やグラフィックスなどもあり豊富である。9章構成の各章は独立しており,好きな章から読むのがよいだろう。それぞれの章の中では簡単なものから難しいものへアルゴリズムが並べられている。C言語で説明してあるが,プログラミングについては入門レベルでも十分読みこなせる。パズルや数学が好きならばお薦めの一冊である。

プログラムの質は作法で決まる

プログラミング作法
Brian W. Kernighan,Rob Pike 著
福崎 俊博 訳
アスキー 発行
2000年11月
355ページ

 最後に取り上げるのは,アルゴリズムだけでなく,プログラム全体をいかに良くするかについて書かれた良書「プログラミング作法」である。著者の一人Brian Kernighhan(ブライアン・カーニハン)氏は,C言語の開発者でもあり,42ページで紹介したK&Rの著者の一人である。

 この本は,質の高いコードの作成と維持を支援することを目的に書かれており,コードの中での変数や関数の命名規則,インデントの仕方といったコーディング・スタイルから説明を始めている。

 第2章でアルゴリズムとデータ構造を説明しているが,アルゴリズムがたくさん紹介されているわけではない。アルゴリズムの基礎,C言語の標準ライブラリにある関数で置き換えられるものなどを説明しており,どうすれば効率良く処理できるかを解説している。

 以降の章では,デバッグ,テスト,性能のチューニング,移植性の向上など,プログラムを改善するための注意事項が豊富に盛り込まれている。この本で説明されていることは特に言語を限定しているわけではないが,掲載されているコードはすべてCであり,一通りCの学習を終えている必要がある。本書を読めば,胸を張って人に見せられるコードを書けるようになるだろう。