プログラマが知るべき97のこと/正しいアルゴリズムとデータ構造を選ぶ
多数の支店を持つ大銀行が窓口業務のために新しいコンピュータを導入しました。しかし、その処理はあまりに遅く、日々不満が募っていました。まだオンラインバンクなどはない頃で、ATMも現在のように広く使われるようになる前の話です。銀行を直接訪れて手続きをする人が今よりはるかに多く、コンピュータが遅いとたちまち長蛇の列ができてしまいました。いら立った銀行はついには、「このままだと契約を破棄する」とコンピュータのベンダを脅し始めました。
ベンダは、遅延の原因を突き止めるべく、パフォーマンス解析とチューニングのスペシャリストを銀行に送り込みました。それでわかったのは、端末上で動くあるプログラムが、1つでCPUキャパシティのほとんどすべてを消費していたということです。プロファイリングツールを使い、そのプログラムについて詳しく調べた結果、問題を引き起こしている関数が特定できました。関数のソースコードは次のようになっていました。
for (i=0; i<srtlen(s); ++i) {
if (... s[i] ...) ...
}
文字列sは、平均でも数千文字の長きになります。このコード(実は銀行側が書いたものでした)は即座に修正され、銀行の窓口業務は滞りなく進むようになりました。
上の例の場合は、必要もないのに、一度に扱うデータが極端に大きくなってしまうところが問題だったわけですが、ではどうすればこういう問題の発生は防げたのでしょうか。
このコードでは、strlenが呼び出される度に、終端のnull文字に到達するまで、文字列 中の数千もの文字一つ一つが調べられることになります。そしてその際、文字列に変更が加えられることは決してないのです。もし、下のように、文字列の長さが先に確かめられるコードになっていれば、strlenが数千回呼び出される(つまり百万回単位で同様の処理が繰り返される)ということにはならなかったはずです。
n=strlen(s);
for (i=0; i<n ++i) {
if (... s[i] ...) ...
}
「まずは動かすこと。速くするのはその後でいい」という格言を知っている人は多いでしょう。局所的な最適化の落とし穴を避けるためには、この格言の心に留めておくことが大切です。しかし、先の例のようなコードを見ると、「遅くても何でもいいからとにかく動かせ」というマキャベリ的な発想でコードを書いているのではないか、と疑ってしまいます。
この種の「何も考えていないようなコード」は実はかなり多く見つかります。「車輪の再発明をするな」とよく言われますが、ここで言いたいのは、単にそういうことではありません。経験の浅いプログラマには、深く考えることなく、とにかく次々にコードを書いてしまう傾向があります。そして、その間にバブルソートなどのアルゴリズムを「発明」してしまうことがあるのです。それで自分が良いコードを書いたと信じ込みます。
適切なアルゴリズムを選ぶことは大切ですが、それには、適切なデータ構造を選ぶということも含まれます。データ構造の違いはプログラムの処理に大きな影響を与える可能性があるからです。たとえば、検索すべき項目の数が百万にもなる時には、リンクリストを使うか、ハッシュを使うか、それともバイナリツリーを使うかで、プログラムに対するユーザの評価はまったく変わることになるでしょう。
プログラマは一般に、車輪の再発明をすべきでなく、可能であれば既存のライブラリを利用すべきと言われます。しかし、上の銀行のような問題が起きないようにするには、それだけではなく、既存のアルゴリズムについて、そのスケール特性について、学ぶ必要があります。一見魅力的だけれど、うかつに使うと最新のテキストエディタでも1980年のWordStarのような昔のプログラム並みに遅くなってしまうような機能もあるのです。プログラミングにおける「再利用」を重視する人は多いですが、いつ、何を、どのように再利用すべきかがわからなければ、良い結果にはなりません。それをわかるためには、問題領域について、またアルゴリズムとデータ構造について、十分な知識が必要なのです。
一般には「良くない」とされているアルゴリズムもありますが、優れたプログラマであれば、そういうアルゴリズムでさえも状況によっては良い結果を生むと知っています。たとえば、問題領域の性質上、扱う項目の数が絶対に5を超えることはないとあらかじめわかっていれば、項目のソートに際しても、5より大きい項目数を考える必要はありません(例:「ヤッツィー: Yahtzee」というゲームでは、サイコロの数が5つと決まっている)。その場合には、バブルソートが最も効率的なソートアルゴリズムということになるかもしれません。どんな道具にもそれに合った使い道というのはあるのです。
アルゴリズムやデータ構造に関しては良い本が何冊かあるので、是非とも読んで、内容を完全に理解しましょう。読むべき本の例としては、Donald Knuthの「The Art of Computer Programming」(有澤誠 他訳、アスキー)などがあげられます。この本は素敵なことに、よく読んで、もし運良く著者の誤りを発見して報告すれば、2ドル56セントの小切手が受け取れます(256セントは、16進数なら100セント、つまり1ドルだから、ということで2ドル56セントになったようです)。