> For the complete documentation index, see [llms.txt](https://y-meguro.gitbook.io/reading-record/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://y-meguro.gitbook.io/reading-record/algorithms/programming_pearls.md). # 珠玉のプログラミング ## 概要 ### 本 * [珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造](https://amzn.to/2wcMOS0) ### かかった時間 * 13.8 時間 ### 進め方 * 演習は気になった問題だけ、ほぼやっていない ### 感想 * 特に印象に残ったこと * プログラミングの前、途中、終わってからもよく考えること * 問題をきちんと定義し、正しく理解すること * 最初のアイデアに飛びつく前に、より良いやり方がないか考える（正しく怠ける） * 入力、出力、中間のデータ構造を徹底的に理解し、適切なデータ構造を利用する * フェルミ推定でチェックすること * 計算回数を減らすために * 記録する、再帰を利用する、データの持ち方を工夫する * コードチューニングはめったに行うものではない、改良したら実験する * 何かを犠牲にする前に、最初の方法をあらゆる方法で改善するテクニックを探すべき ## 読書メモ ### 序文 * この本のコラムを読み進めるにあたって、言っておくべきことが 1 つあります * それは「急ぎすぎないでください」ということ ### 第 1 部: はじめに * 最初の 5 つのカラムでプログラミングの基礎を考える ### 1. 真珠貝を開いて * ケース * はじめの質問 * 「ディスクでのソート方法を教えてもらえませんか」 * 問題の正確な定義 * 入力 * ファイルは最大 n 個の正の整数を含んでいる。整数はそれぞれ n より小さく、n = 10^7 である。入力で同じ整数が現れたら決定的なエラーとなる。整数に他の情報は付随しない * 出力 * 入力された整数を昇順にソートした一覧 * 条件 * ディスクには大きな容量の空きがあるが、メインメモリには 1 メガバイト程度の余裕しかない。実行時間は長くて数分。10 秒を切る必要はない * ポイント * 最大 1000 万個の異なる整数を大体 800 万ビットで表せるか * 1000 万ビット使えるなら「入力ファイルに整数 i があれば i 番目のビットを 1 にする」という方式で解ける ``` // セットを空にする for i = [0, n) bit[i] = 0 // 対応する要素をセットに入れる 入力ファイル中にある整数 i に対し bit[i] = 1 // ソートされた出力を作る for i = [0, n) if bit[i] == 1 i を出力ファイルに書く ``` * 教訓 * 小さな問題の注意深い分析が、ときに驚くほどの実益を生む * 原則 * 正しい問題 * 問題をきちんと定義することで、ことの 90% がすむと言える * ビット列というデータ構造 * ビット列は「限られた範囲内にあり、密で、重複がなく、付随する情報もないようなデータのセット」を表すのに有効 * また、これらの条件が満たされない場合でも、データ表のインデックスに、このような構造が使えることもある * 多パスのアルゴリズム * 入力データを何回か読み直し、少しずつ処理を進めていくアルゴリズム * 実行時間と使用メモリのトレードオフとそうでないもの * トレードオフとなることも多いが、私の経験では「使用するメモリを小さくすることで実行時間も小さくなる」ことのほうが多い * 単純な設計 * 「設計が完璧だと思えるのは、もうこれ以上付け足すものがないときではなく、もうこれ以上取り去るものがないときだ」 ### 2:「ああ(そうか)！」アルゴリズム * 「ああ(そうか)！」というひらめきは、よく勉強して得られるというものではない。しかし、プログラミングの前にも、途中にも、また終わってからもよく考えるプログラマなら誰でも経験できるもの * 3 つの問題 * A: 最大で 40 億個の 32 ビット整数がでたらめな順に入っているファイルがある。このファイルに入っていない 32 ビット整数を 1 つ見つけられるか。メインメモリが非常に大きい場合はどうするか。また、外部に作業ファイルを作ることはできてもメインメモリには数百バイトほどの余裕しかないときはどうするか * B: 要素が n 個ある配列を左方向に i 要素分回転させるにはどうすればいいか。例えば n = 8 で i = 3 の時、配列 abcdefgh を defghabc にする。単純には n 個の作業用配列を作って n ステップで仕事すればよいが、メモリを数十バイトしか使わずに実行時間も n に比例するだけのように回転させられるか * C: 英語の辞書が与えられた時に、すべてのアナグラムを見つけられるか。例えば、pots、stop、tops は同じ文字を入れ替えているだけなのでアナグラムとなる。つまり、単語の集合が与えられて、すべてのアナグラムが見つけられればよい * A について * 入力される整数の個数を n とする * n に比例する回数で問題を解けるか * メインメモリが大きい場合はコラム 1 のようにビット列の方法で解ける。メインメモリに余裕が少ない場合にはどうするか * ソートを利用する場合、`n log n` に比例する * 解 * やり方 * 32 個のビット列の 2 分探索の問題と考えるとわかりやすくなる * 最初のビットが 0 のものと 1 のものにわけて、2 つのファイルに書き込んでいく * 処理が終わった時に、最大で 20 億個の整数が書かれる * 次に、出力されたファイルで整数の個数の少ない方を新しい入力ファイルにし、今度は 2 番目のビットを見て、また 2 つのファイルに分ける * これを繰り返す * 実行時間 * 最初は n 回の読み込み、次は n/2 回、... と続くので実行時間は n に比例する * B について * いくつかやり方がある * 順々に移動させていく * 前の部分と後ろの部分を入れ替える * これらでも条件を満たして解くことはできるが、やや複雑でデリケートなコーディングになる * 解 * ab から ba を作ると考える * a を逆向きにしたものを a^r とすると * (a^r b^r)^r は ba となる * これは再帰的に解くことができ、ミスもしにくいコードとなる * C について * 3 つの段階で考える * sign * 各英単語の文字をソートして、それを「印」とする * sort * sign で作成した印に従ってソートする * squash * sort で同じ印を持つものが連続しているので、それらをまとめる * 原則 * ソート * ソートの明らかな使い道は、整列された出力を作ること * しかし、ソートの用途はこれだけではない * アナグラムの問題では、同じ要素をまとめるためにソートを利用した * 2 分探索 * 2 分探索はソートされたデータ中での探索方法として非常に有効で、メインメモリ上とディスク上のどちらでも使える * 唯一の問題点は、データの全体がはじめからわかっており、しかもソートされている必要があるということ * 印 (シグナチャー、署名) * 同値関係によって定義されたクラスに、ある要素が属するかどうか調べるのに印を定義しておくと便利 * 問題を解く見通し * 良いプログラマは少々怠け者 * 最初のアイデアに飛びつく前に、椅子の背にもたれて、何かひらめかないか待ってみる * もちろん時間配分を身につけることも大事 * このようなスキルは問題を解き、その解法をまた考え直す、そういう経験を積むことによって得られるもの ### 3: データで決まるプログラムの構造 * どうして小さなプログラムで十分なのに、大きなプログラムを書いてしまうのか * 1 つは「怠け癖」がないため最初に思いついたアイデアに飛びついてしまうことだが、他にも多くの理由が考えられる * 心理的な障害があって、思いつかない * 元のプログラムを改善したことに満足して、すぐ目の前にある改善点を見落としてしまう * 教訓 * 小さいプログラムで済む問題に、大きなプログラムを書くな * アドバイス * メモリが足りなくなって途方にくれているプログラマは、プログラムからちょっと離れ、椅子の背にもたれて、データについて考えてみると良い * 表現こそがプログラミングの本質 * 椅子の背にもたれた時に考えるべき原則 * コードの繰り返しには配列を使え * 複雑な構造はカプセル化せよ * 可能なら優れたツールを使え * データによってプログラムの構造を決めよ * 適切なデータ構造のおかげで複雑なプログラムが小さくなることがあるように、データがプログラムの構造を決めうる * 優秀なプログラマは、コードを書く前に、そのプログラムの入力、出力、中間のデータ構造を徹底的に理解する ### 4: 正しいプログラムを書く * 原則 * 表明 * 表明 = assertion。プログラムの動作に関係のない「コメント」と考えて良い * 入力と変数と出力の関係は、プログラムの「状態」を表している * 表明を使うことで、プログラマはそのような関係を正確に示すことができる * 逐次実行の制御構造 * 「まずこれをやれ、次にこれをやれ」というプログラムの最も簡単な構造 * この場合、命令の間に表明を挿入し、その構造を理解できる * またプログラムの処理を段階的に調べられる * 選択実行の制御構造 * if や case を含む構造。いくつかの選択肢の中の 1 つが実行される * このような構造でコードの正しさを見るには、それぞれの選択肢を個別に調べなければならない * あることが選択される場合も、表明を使って検査できる * 繰り返し実行の制御構造 * 「不変な表明」がループのはじめに成り立つことと、繰り返しの各ステップの後でもそれが成り立つことを調べる * これらをあわせて「ループが終了する時に、正しい結果が得られる」ことが示せる * 関数 * 2 つの表明で示す * 「前提条件(前状態)」が正しいこと * 「結果(後状態)」が正しいこと * プログラム検証の役割 * プログラム中にある表明の 1 つの利点は、プログラマの理解を明文化すること * プログラムの重要な説明は表明という形で記述されるが、実際にどのような表明がいいかは、経験を積んでわかってくるもの * デバッグをするときは、コードと誤った表明の両方を直すようにする * 表明はプログラムの保守管理にも重要 * 何年間も放って置かれた初めて見るコードの保守を任された場合、表明はそのプログラムを理解するのに役立つ * ただし、あくまでもコードを単純に保つことが、正しくプログラムするための中心 * 上記のテクニックはごく一部 * 一方、これらのテクニックをよく知っているプロのプログラマは「プログラムでは、難しい部分が最初に動き、バグは易しい部分によくある」ということも聞く ### 5: あと少しの事 * 原則 * 足場 * 元の関数をチェックするためのコード * 最も良いプログラムテストのための「足場」は、簡単に書けるもの * コード化 * まずわかりやすい擬似コードを書いて、それを実際のプログラム言語に翻訳する方法が最も簡単だと思われる * テスト * 大きなシステムの中でより、「足場」の中でのほうが、簡単にしかも徹底的にテストできる * デバッグ * プログラムが「足場」の中に孤立しているとデバッグは難しいものだが、実際の使用環境の中にある場合はもっと難しい * 実行時間の計測 * もし実行時間が問題にならなければ、逐次探索のほうが 2 分探索よりはるかに簡単 * コードが完成したら、実行時間が実際に予想通りであるかどうか調べる必要がある ### 第 2 部: パフォーマンス * ユーザーを喜ばせ、開発者を悩ませない、単純で強力なプログラム、それこそがプログラマの究極のゴール * ここから視点を変え、優れたプログラムの 1 つの側面である、効率について考える * パフォーマンスを考える理由 * 多くのアプリケーションにとって本質的 * プログラマにとって良い勉強になる ### 6: パフォーマンスに関する考察 * Appel がスピードアップのために工夫したこと * アルゴリズムとデータ構造 * 木のデータ構造を使って 1 ステップのコストを O(n^2) から O(n log n) に改善した * アルゴリズムチューニング * まれにしか起きない特別なケースは、特別な関数で処理した * データ構造の再構成 * 最初に作った木構造は、時間ステップが経っていくと不適切なものとなっていた。時間ステップごとに木構造を作り直すようにした * コードチューニング * 木構造を使うおかげで精度があがるので、64 ビットの倍精度浮動小数点数を 32 ビットの単精度浮動小数点数にできた。これにより実行時間が半分になった * ハードウェア * デザインレベル * 問題定義 * 問題をきちんと定義すると、プログラムがもともと思っていたほど大掛かりでなくて良いとわかることもある * システム構造 * 大きなシステムをいくつかのモジュールに分解することは、パフォーマンスに関して、おそらく単独ではもっとも決定的なファクターとなる * アルゴリズムとデータ構造 * コードチューニング * システムソフトウェア * ソフトウェアそのものよりも、そのソフトウェアが動いているシステム(OS)を変えるほうが簡単な場合もある * ハードウェア * 原則 * 少々のスピードアップが必要なら、最善のレベルを 1 つ選んで考える * 非常に大きなスピードアップが必要なら、すべてのレベルを考える * しかし、どのレベルを考えている時も、全体像は見失わないようにする ### 7: 封筒の裏で… * 封筒裏の計算 * 使用済みで不要になった封筒の裏でも使って、簡単にできてしまう計算 * フェルミ推定と同じ * 1 つの答えより 2 つの答えのほうがよい * 複数の計算方法で比較することは重要 * 簡単なチェック * 単位のチェック、桁のチェック、常識との照らし合わせ * 速算ルール * 例えば「72 の法則」というのがある。y 年間、利率 r% でお金を貯金し続ける。もし y × r = 72 ならお金はほぼ倍になっている * 実際、利率 6% で 12 年間貯金しておくと、2.012 倍になる。利率 8% で 9 年間貯金しておくと、1.999 倍になる * 練習 * 他の多くのことと同様に、この計算のスキルは練習によってのみ向上する * 安全係数 * 必要とされるものの何倍かの係数をかける * Roebling は自身の無知を補うために、必要とされるものの 6 倍の強度の橋を作った * リトルの法則 * キュー内にあるものの個数は、入ってくる率と平均的な待ち時間の積に等しい * 原則 * Einstein のアドバイス * 「何でも可能な限り単純に考えるべきです。しかし、単純すぎないように」 ### 8: アルゴリズムデザインのテクニック * 問題 * n 要素の浮動小数点数の配列 x を入力とし、配列 x の連続した要素でその和が最大になるものを見つけ、その和を出力する * 3 乗のアルゴリズム * n が 10000 の時 22 分かかり、n が 100000 の時 15 日かかる ``` maxsofar = 0 for i = [0, n) for j = [0, n) sum = 0 for k = [i, j) sum += x[k] // sum は x[i..j] の和 maxsofar = max(maxsofar, sum) ``` * 2 乗のアルゴリズム * 2 つある ``` maxsofar = 0 for i = [0, n) sum = 0 for j = [i, n) sum += x[j] // sum は x[i..j] の和 maxsofar = max(maxsofar, sum) ``` ``` cumarr[-1] = 0 // cumarr には x[0..i] の和が格納される for i = [0, n) cumarr[i] = cumarr[i - 1] + x[i] maxsofar = 0 for i = [0, n) for j = [i, n) sum = cumarr[j] - cumarr[i - 1] // sum は x[i..j] の和 maxsofar = max(maxsofar, sum) ``` * 分割して征服するアルゴリズム * アイデア * 配列を前半と後半にわけて、どちらかにあるか、またはまたがっているか * 実行時間は O(n log n) ``` float maxsum3(l, u) if (l > u) // 要素がない場合 return 0 if (l == u) // 1 要素の場合 return max(0, x[l]) m = (l + u) / 2 lmax = sum = 0 // 境界から左側に伸びる部分配列の和の最大値 for (i = m; i >= 1; i--) sum += x[i] lmax = max(lmax, sum) rmax = sum = 0 // 境界から左側に伸びる部分配列の和の最大値 for (m, u] sum += x[i] rmax = max(rmax, sum) return max(lmax + rmax, maxsum3(l, m), maxsum3(m + 1, u)) answer = maxsum3(0, n - 1) ``` * 走査アルゴリズム * アイデア * 配列の左端の x\[0] から右端の x\[n - 1] まで、常にそこまでの部分配列の和の最大値を記録しながら走査する * いま x\[0..i-1] についてこの問題の解がわかっているとする。x\[i] に拡張することを考える * i 要素中で要素の和が最大になる部分配列は、i - 1 要素中で要素の和が最大になる部分配列(maxsfar という変数に記録する)か、i 番要素で終わる部分配列中で要素の和が最大になるもの(maxendinghere という変数に記録する)のどちらか * 実行時間は O(n) ``` maxsofar = 0 maxendinghere = 0 for i = [0, n) // 不変な表明: maxendinghere と maxsofar は x[0..i-1] について成立している maxendinghere = max(maxendinghere + x[i], 0) maxsofar = max(maxsofar, maxendinghere) ``` * 原則 * 状態を記録し、再計算を避ける * データを前処理してまとめる * cumarr に部分配列の和を記録した * 「分割して征服」アルゴリズム * 走査アルゴリズム * x\[0..i-1] の答えから x\[0..i] の答えをどう探すか * 累計 * 実行時間の下限 * 自分のアルゴリズムが「実行時間の下限」であることを示すことで安心して眠れる ### 9: コードチューニング * これまでは効率に関する高レベルなアプローチを考えた。ここでは低レベルなアプローチを考える * 原則 * コードチューニングの最も重要な原則は「コードチューニングはめったに行うものではない」ということ * 効率(スピード)の役割 * 未熟な最適化がたくさんの問題を引き起こす * 正確さや機能や保守管理のしやすさを犠牲にしてしまう * 効率は問題になるまで、考えないほうがよい * 測定用のツール * プロファイルは決定的な場所を指す * 「壊れていなければ、直すな」 * デザインのレベル * コードチューニングに行く前に、他のアプローチを検討する * スピードアップのつもりがスローダウンに * 「改良」をしたら、もっともらしい入力で実験してみる必要がある ### 10: メモリの節約 * 単純であることが、機能性・堅牢性・スピード・メモリ節約につながる * データ空間でのテクニック * 記憶させずに再計算させる * 疎なデータ構造 * データ圧縮 * データをコンパクトに符号化してメモリを節約する * メモリ確保(割付)の方針 * 必要になるまでメモリを確保しない * プログラムコードが使うメモリの節約 * 関数の定義 * コード中によく現れるパターンを関数化することで、プログラムを簡単にし、それゆえ必要なメモリを減らし、また理解しやすいものにできる * インタープリタ * マシン語への翻訳 * 原則 * メモリのコスト * メモリの節約を始める前に、メモリのコストを考えるべき * あと 10% 余分にメモリを必要とする場合、何も問題ないのか、メモリが不足してしまうのか * 頻繁に使われる部分 * データにも「頻繁に使われる部分」がある * メモリの空きを測定する * パフォーマンスモニターを利用する * トレードオフ * プログラマはパフォーマンスや保守管理性のために、メモリを多く使うこともある * このような場合もあるが、その他のすべての可能性を検討した上でなされるべき。何かを犠牲にする前に、最初の方法をあらゆる方法で改善するテクニックを探すべき * 環境に従う * 自分のプログラムがシステムに逆らったことをしていないか * 仕事に適切なツールを * 「データ空間でのテクニック」、「プログラムコードが使うメモリの節約」のすべてのオプションを考えるべき ### 第 3 部: 作品 ### 11: ソート * 基本はライブラリのソート関数を使う。ただし、ライブラリのソート関数が使いづらい場合や、特定の問題に遅すぎる場合には自分でソート関数を書かなければなならない #### 挿入ソート * 実行時間は O(n^2) ``` 擬似コード for i = [1, n) // 不変な表明: x[0..i-1] はすでにソートされている // ゴール: x[i] を x[0..i] 内の適当な場所までずらしていく ``` ``` 単純なコード for i = [1, n) for (j = i; j > 0 && x[j - 1] > x[j]; j--) swap(j - 1, j) ``` ``` 改善したもの for i = [1, n) t = x[i] for (j = i; j > 0 && x[j - 1] > t; j--) x[j] = x[j - 1] x[j] = t ``` #### クイックソート ``` 擬似コード void qsort(l, u) if l >= u then // ソートする配列の要素数が 1 個以下の場合は何もしない return // ゴール: 特定の値で配列を分割する。その特定の値は最終的には位置 p に収まるとする qsort(1, p - 1) qsort(p + 1, u) ``` ``` 簡単なクイックソート void qsort1(l, u) if l >= u then return m = l for i = [l + 1, u] // 不変な表明: x[l+1..m] < x[l] && x[m+1..i-1] >= x[l] if (x[i] < x[l]) swap(++m, i) swap(l, m) // x[l..m-1] < x[m] <= x[m+1..u] qsort(1, m - 1) qsort(m + 1, u) ``` ``` 改善したクイックソート void qsort4(l, u) if u - 1 < cutoff return swap(l, randint(l, u)) // ランダムにピボットを選ぶ t = x[l]; i = l; j = u + 1 loop do i++; while i <= u && x[i] < t do j--; while x[j] > t if i > j break temp = x[i]; x[i] = x[j]; x[j] = temp swap(l, j) qsort4(l, j - 1) qsort4(j + 1, u) ``` ### 12: サンプリング問題 * 問題 * 2 つの整数 m と n で m < n を満たしているものを入力とし、0 .. n - 1 の範囲の m 個のランダムな整数を大きい順に並べたものを出力とする。ここで出力される整数に重複はないものとする * 1 つの解 ``` void genknuth(int m, int n) { for (int i = 0; i < n; i++) { // 残りの n - i 個から m 個選択する if ((bigrand() % (n - i)) < m) { cout << i << "\n"; m--; } } } ``` * もともと空のセットにランダムな整数を必要なだけ挿入する方法もある * 以下は C++ の STL の set を使う場合は以下 ``` void gensets(int m, int n) { set S; while (S.size() < m) { S.insert(bigrand() % n); } set::iterator i; for (i = S.begin(); i != S.end(); ++i) { cout << *i << "\n"; } } ``` * 配列のシャッフルを使う場合 ``` void genshuf(int m, int n) { int i, j; int *x = new int[n]; for (i = 0; i < n; i++) { x[i] = i; } for (i = 0; i < m; i++) { // 最初の m 要素だけシャッフルすればよい j = randint(i, n - 1); int t = x[i]; x[i] = x[j]; x[j] = t; } sort(x, x + m); for (i = 0; i < m; i++) { cout << x[i] << "\n"; } } ``` * 原則 * 問題を理解する * 問題を抽象的(本質的)に述べる * 問題をきちんと述べることで、まず問題の解決方法が見えてくる * デザイン空間を調べる * 解をコード化する * 考え直す ### 13: 探索 * セットを表現するのに重要な 5 つのデータ構造を見る * ソートされた配列 * ソートされたリスト * 2 分探索木 * ビン * ビット配列 * 原則 * ライブラリの役割 * データ構造の問題に行き当たったら、まずその問題を解くための一般的なツール(ライブラリにあるデータ構造)を探してみるとよい * メモリの重要性 * コードチューニング ### 14: ヒープ ``` void shiftup(n) // 前提条件: n > 0 && heap(1, n - 1) // 結果: heap(1, n) i = n loop // 不変な表明: i とその親の関係を除くと、heap(1, n) が成立している if i == 1 break p = i / 2 if x[p] <= x[i] break swap(p, i) i = p ``` ``` void shiftdown(n) // 前提条件: heap(2, n) && n >= 0 // 結果: heap(1, n) i = 1 loop // 不変な表明: i とその子(0 個か 1 個か 2 個ある)との関係を除くと heap(1, n) が成り立つ c = 2 * i if c > n break // c は i の左側の子 if c + 1 <= n // c + 1 は i の右側の子 if x[c + 1] < x[c] c++ // i に子が 2 つある場合は、c は小さい方の子 if x[i] <= x[c] break swap(c, i) i = c ``` ``` void insert(t) if n >= maxsize // エラー報告 n++ x[n] = t // heap(1, n - 1) が成り立つ siftup(n) // heap(1, n) が成り立つ ``` ``` void extractmin() if n < 1 // エラー報告 t = x[1] x[1] = x[n--] // heap(2, n) が成り立つ siftdown(n) // heap(1, n) が成り立つ return t ``` * 原則 * 効率 * 正しさ * ヒープに作用する関数は、作用前に 2 つの性質を仮定し、作用後もこの 2 つの性質が成り立っていることを保証しないといけない * 抽象化 * 手続きの抽象 * ソート関数を使って配列をソートする時、その関数の中身のコードを知っている必要はない * データ型の抽象 ### 15: 真珠の列 * 文書中単語が何回現れるか数えるプログラム ``` int main(void) { map M; map::iterator j; string t; while (cin >> t) { M[t]++; } for (j = M.begin(); j != M.end(); ++j) { cout << j->first << " " << j->second << "\n"; } return 0; } ``` * 原則 * 文字列の問題 * 文字列のデータ構造 * ハッシュ表 * バランスした木 * サフィックス配列 * ライブラリを使うか自家製のコンポーネントを使うか ### 第 1 版のエピローグ * プログラマへの 10 の提案 * 正しい問題を考えよ * いろいろな解法を比較検討せよ * データをよく見よ * 「封筒裏の計算」を使え * 対称性を利用せよ * コンポーネント(部品)を考えてデザインせよ * 試作品を作れ * 必要なら、妥協せよ * プログラムを複雑にしてはいけない * エレガントに