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

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

CleanCodeなど今までの技術書とは毛色が異なり、特定の言語に限らない、アルゴリズムとデータ構造について論じている。 第1部から第3部の全15のコラムに分かれている。

• 第1部 コラム1~5 プログラミングの基礎である、問題定義、アルゴリズム、データ構造、プログラムの検証とテスト
• 第2部 効率に関するコラム
• 第3部 今までのテクニックをソート、探索、文字列などの重要な問題に応用

コラム1 真珠貝を開いて

重複のない単純なデータのソートを、ビット列というデータ構造を用いて実現する。

例題

入力ファイルには、重複のない7桁の正の整数が記録されている。
入力された整数を昇順にソートした一覧を出力したい。
ただし、メモリには1MB程度の余裕しかない。

解

ビット列で実現！

原則

正しい問題
問題定義をきちんとする。アルゴリズム、データ構造を考える上で、問題の前提条件などきちんと整理する。
ビット列というデータ構造

ビット列は、「限られた範囲内にあり、密で、重複が無く、付随する情報もないようなデータのセット」を表すのに有効です。

例えば、20より小さい整数を、20個のビット列で表すことができる（整数nが存在する場合、ビット列のn番目のフラグを立てる）

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

ひらめきが大事。

例題

例題1
最大40億個の32ビット整数がでたらめな順に入っているファイルから、このファイルに含まれていない整数を探し出す。
例題2
要素がn個の配列を左方向にi要素分回転させる。
例題3
英語の辞書が与えられたときに、すべてのアナグラムを見つける。

解

2分探索、（まとめるための）ソート、印付け（値を同値クラスに振り分ける）

原則

ソート
ソートの用途は、整列された出力を作るだけではない。
2分探索
ソートされたデータの探索方法として非常に有効。あらゆる場面で使われる。
印（シグネチャ、署名）
ある値を決まったルールでグループにわけ、印をつけておく。その印で、ソートするなどして効率的に処理できる。
ここでは、アナグラムの検索を実現している。