KeN's GNU/Linux Diary

2006年12月05日

『珠玉のプログラミング』

アルゴリズムは「有限の手続きであり、定まった一組の記号で書かれ、厳密な指令に支配され、1、2、3……という個々のステップを踏んで進み、これを実行するのに、洞察力も才気も直観も知性も明敏さも必要なく、遅かれ早かれ、終わりにいたる――そのようなものである」(『史上最大の発明アルゴリズム』から引用)。

本書は、ソートや探索といった、コンピュータプログラミングをする上でよく課題となりボトルネックとなりやすいアルゴリズムを重点的に取り上げ、既存の犯しがちな効率の悪い――“頭が固い”と言ってもよいか――コードから、柔軟な頭で発想を転換することによっていかに効率的に劇的に改善されたコードに変えられるかを示している。根底にあるのは、O(n²)のようなnの増加に耐えられない関数アルゴリズムから、いかにしてO(logn)あるいはO(n logn)程度に落とし込むかだ。

提示されているテクニックはまったくの新基軸というものではなく、あぁなるほど!(本書の言葉を借りるなら「Aha!」)という、一見難解で太刀打ちできそうもないようなパズルを発想の転換で解き明かされたような驚きがある。

情報系の知識がないまま単に読んでいるだけだと、いまいち退屈に見える本かもしれない。掲載されている疑似コードを適当な言語で実際に実装して、時間を測定したり入力値を調整したりコードを改造したりと手を動かしてみることで、本書が自身を珠玉と呼ぶだけの輝きが表出し、読者の知識に取り込まれることだろう。

冒頭で引用の書籍も紹介しておこう。記号論理学と物語の組み合わせで、文体も凝りまくっていてかなり難解。まだほとんど読めていない。

リンク