ビブリオ・トーク -私のオススメ-：珠玉のプログラミング -本質を見抜いたアルゴリズムとデータ構造-

全文

(1)連載. ビブリオ・トーク. ─ 私のオススメ─. ⇢ 松崎公紀（高知工科大学）. 珠玉のプログラミング. ─本質を見抜いたアルゴリズムとデータ構造─. Jon Bentley 著，小林健一郎訳ピアソン桐原（現在は丸善出版）（2000），305p.，3,400 円＋税，ISBN : 978-4-621-06607-2. プログラミングの面白さを伝えたい. 出版され，ほとんどのコラムが書き直されている．. 私の大学では，学部 1 年生で C プログラミング. 第 2 版からも時間がたっているため，多少本文に. から始まり，3 年生を対象としたソフトウェア工学の. 出てくる計算機などが古いことがあるが，本書の内. PBL（Project-Based Learning 課題解決型学習）演習. 容は十分現在においても有効である．. など，多くのプログラミングに関する講義・実験・演. この本は，以下の 15 のコラムから構成される．. 習を行っている．学生は，それらの講義でプログラミ. 第 1 部（コラム 1 〜 5）は，プログラミングの基礎. ングを学んで研究室に入ってくる．しかしながら，最. として，問題定義，アルゴリズム，データ構造，検. 近，ライブラリや Web 上のコード片など，すでにあ. 証とテストについて広く述べられている．第 2 部. るパーツを組み合わせることはできるものの，自分で. （コラム 6 〜 10）は，効率（パフォーマンス）を中. 解法を考えることができない（できなくなっている）よ. 心にまとめられている．第 3 部（コラム 11 〜 15）は，. うな印象がある．もちろん，あるものを組み合わせて. それまでのテクニックの応用に関するものとなって. 動く（見映えのする）ものを作れることはよいことで. いる．この本では，単にプログラムやアルゴリズム. あるが，大学における研究目的のプログラミングでは，. の説明がされるのではなく，例題に対してアルゴリ. それでは困ることが多い．そこでプログラムの改善を. ズムをどのように応用すればいいか考えていくもの. 促してみるのだが，ライブラリや Web 上のコードを使. となっており，実学に基づいた学習ができる．. うこと以上を考える手前で思考停止してしまうようだ．私は，広い意味のプログラミングは問題定義，デ. コラム 1：真珠貝を開いて. ザイン，実現，および，評価を含むクリエイティブ. コラム 2：「ああ（そうか）！」アルゴリズム. な仕事であると考えている．そのような中には苦労. コラム 3：データで決まるプログラムの構造. もあるが，課題を解決できたときには喜びもある．. コラム 4：正しいプログラムを書く. このような考えを，どうにか学生に伝えたい．しか. コラム 5：あと少しの事. し，実際のところ，そう簡単でもない．. コラム 6：パフォーマンスに関する考察. 今回紹介する「珠玉のプログラミング」は，クリ. コラム 7：封筒の裏で .... エイティブなプログラミングへと足を踏み出したい. コラム 8：アルゴリズムデザインのテクニック. 人に，じっくり読んでもらいたい本である．. コラム 9：コードチューニング. この本の歴史と概要. 410. コラム 10：メモリの節約コラム 11：ソート. この本は ACM の学会誌「Communications of. コラム 12：サンプリング問題. the ACM（CACM）」に「Programming Pearls」とし. コラム 13：探索. て連載されたコラムをもとに作られた本であり，第. コラム 14：ヒープ. 1 版は 1986 年に出版された．第 2 版は 2000 年に. コラム 15：真珠の列. 情報処理 Vol.55 No.4 Apr. 2014.

(2) 連載. ビブリオ・トーク. ─ 私のオススメ─. 工学的アイディアの詰まった本である. 評価を行う方法と，その重要性が述べられている．. この本の内容から，私の好きなところを 3 つ紹. このコラムにある考え方やテクニックは，私生活に. 介しよう．これらはいずれも工学的アイディアが凝. おいても役立っている．. 縮されている．. 実際大学で学生の研究指導を行う過程でも，これ. コラム 1 の最初に，著者が受けた次の質問が書. らのアイディアを活用できる場面によく遭遇する．. かれている．「ディスクでのソート（整列）方法を教. 最近の例を 1 つ示そう．大貧民プレイヤに関して. えてもらえませんか？」あなたならば，どう答える. 研究を行っている学生がプログラムを書いたが，ど. だろうか．私の最初の解答は，「マージソートを行. うにも予想より数倍遅かった．そこでコードを一緒. えばできる」というものであった．これは，上の質. に読んでみたところ，まさにコラム 1 のような状. 問に対する一般論としては正しいものである．しか. 況になったのである．トランプのカードをランダム. し，質問者の求めていたものとは異なるものであっ. に配る部分が，正しくはあるのだけれども全然洗練. たという．詳細は省略するが，コラムでは，質問者. されていなかった．そこで，工夫されたやり方を示. が求めていたこと（問題）の正確な定義を行い適切. してプログラムを改良したところ，まさに驚くほど. なデザインを行うことで，上のマージソートよりも. の改善となった．. ずっと良いものへと到達する過程が示されている．（驚くべきことに，最後はメインメモリ上で動作す. 良書は長く価値がある. る単純な 2 つのループからなるアルゴリズムとな. このビブリオ・トークの企画があがったときに，. っている．実際に読むと，なるほどと思うに違い. 私はまっさきにこの本を思い浮かべていた．その. ない）．. 後 2013 年 8 月に，出版社が技術書／翻訳の業務か. コラム 4 で題材とされているものは，二分探索. ら撤退するというニュースがあり大変驚いた（幸い，. である．プロのプログラマに対して，十分な時間を. この本を含むいくらかの本は丸善出版より再出版さ. 与えて二分探索のコードを書いてもらいその後検証. れることになった）．このような良書はぜひ長く読. したところ，90％ほどの人がバグがあったと答え. まれてもらいたいと願う．. たそうである．このコラムでは，プログラム検証で. （2014 年 2 月 7 日受付）. 培われたアイディアをもとに，正しいプログラムを書くための方策が述べられている．コラム 7 では，封筒の裏ででもできるような簡単な計算「封筒の裏計算（back-of-the-envelope calculations）」を用いて，パフォーマンスに関する. 松崎公紀（正会員） [email protected] 2005 年東京大学大学院情報理工学系研究科中退，同年東京大学助手， 2009 年より高知工科大学准教授．高水準並列プログラミング，アルゴリズム導出のほか，ゲーム情報学に興味を持つ．博士（情報理工学）．. 情報処理 Vol.55 No.4 Apr. 2014. 411.

(3)