珠玉のプログラミングの読書メモ①

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

 コラム1~5まで

■コラム1 真珠貝を開いて

ユーザが本当に望むことをはっきりさせることもプログラミング。

 

要点

• 小さな問題の注意深い分析が、ときに驚くほどの実益を生む
• 手を動かす前に数分考えることで、実行時間と使用メモリのトレードオフなしのいいとこ取りアイディアを思いつくことがある
• {1,2,3,5,8,13} = 0111010010000100000 のアイディア

 

学んだこと

• 入力ファイルをn回読みなおすプログラムのことをnパスのプログラムと呼ぶ

 

■コラム2 「ああ（そうか）！」アルゴリズム

アルゴリズムについて考えると楽しいひらめきがある。「世の中のイケメンは死滅しろ」という願望を再帰的に実行するとlog(n)オーダーの試行回数でアダムが生まれる。

 

要点

• 二分探索はlog(n)で処理できるので早いし楽
• 二分探索と再帰呼び出しは相性が良い
• データをまとめるときは水平、垂直にソートするとシンプルに処理できるかも

 

学んだこと

• while(scanf(%s,word) != EOF){ 処理 }　で入力を一文字づつword変数に代入しながら処理できる

 

■コラム4「正しいプログラムを書く」

プログラムを書く前に擬似プログラムで正しさを検証する。簡単な二分探索のコードでもプログラマーの９割がバグ付きプログラムを提出してくる。

 

要点

• プログラムを書く際の検証の原則→頭がごっちゃにならないように「不変な表明」を重要な所に書いとく
• 「不変な表明」とは、ifやcase、ループなどを使用したプログラム内で、要所要所の状態を記述するprintf文とかそういうの
• 例えば二分探索であれば、求めたい値pの存在範囲はループを繰り返すと狭まっていく。その時々でpはどの範囲にあるべきか？を正確に示すのが不変な表明

 

学んだこと

• 「契約によるプログラミング」とは、ある関数を作成・保守する上で、前提条件の表明と結果の表明を行い、前提条件が満たされていれば結果が保証され、一度この関数の正しさをチェックした後はいちいち関数の中身をチェックしないプログラミングのこと。

 

■コラム5「あと少しのこと」

コードを書いてからが本番。ここをしっかりやらないと二分探索のように16年もバグ付きコードが出版されることになる。

 

要点

• 完全なプログラムを書くためのアプローチ手順

1. アルゴリズムとデータ構造を選ぶ
2.  擬似コードを書く
3.  正しさを「不変な表明」で確かめる
4.  実装する
5.  「足場」でテストし、assert関数でチェックする
6.  入力サイズと実行時間のグラフを作成し、オーダーを確かめる

 

学んだこと

• 「足場」とは、関数の動作テスト用に作った短いコードのこと。入力データも局所的にハードコーディングする。
• assert関数とは、引数が真であったらスルー、偽であったらデバッグするような関数のこと。ライブラリで用意されてるものを使ってもいいし無かったら自分で作る。こいつをプログラムの節々に挟んでもいいし、「足場」でのテストの自動化にも使える。“assert関数を製品版で消し去ってしまうのは、海岸での訓練では救命胴衣を着け、いざ海に出るときにそれを脱いでしまう船乗りのようだ"

 

気になること

• Steve Maguire, "Writing Solid Code”,Microsoft Press,1996の２章にマイクロソフト製品やライブラリに使われている表明の生々しい話が書かれているらしい。