なぜ読もうと思ったのか
あるエンジニアさんがたびたび「プログラミングとはつまるところアルゴリズムとデータ構造だ(意訳)」といったことを言っていたが、いまいちピンと来ていなかったので、自分にはおそらく何か足りない知識があるんだろうと思いこの本を手に取ってみた。
概要
- 訳者まえがき
- なぜこの本を書いたのか
- 第1章 イントロダクション
- 第2章 配列を使ったリスト
- 第3章 連結リスト
- 第4章 スキップリスト
- 第5章 ハッシュテーブル
- 第6章 二分木
- 第7章 ランダム二分探索木
- 第8章 スケープゴート木
- 第9章 赤黒木
- 第10章 ヒープ
- 第11章 整列アルゴリズム
- 第12章 グラフ
- 第13章 整数を扱うデータ構造
- 第14章 外部メモリの探索
各章の内容はタイトルから想像できると思う。
印象に残った/役に立ったところ
この本で一番気に入っているのは「訳者まえがき」で、以下は特にクるものがあった。
>本書で紹介するデータ構造はシンプルなものである。よくある誤解は、これらのデータ構造は理論上のものであり、実際のソフトウェアはもっと複雑なデータ構造を使っているというものだ。これはまったくの間違いである。OSやブラウザなどの複雑なソフトウェアも、その実、シンプルなデータ構造の組み合わせでできている。本書で紹介するデータ構造が理解できれば、多くのソフトウェアの骨子が理解できるようになるだろう。言い換えれば、本書が紹介するのはおもちゃのデータ構造ではなく、現実のプログラムの中で実際に使われているデータ構造である。
内容は、キュー、スタック、配列、連結リスト、ハッシュテーブルといった基本的なデータ構造から始まって、二分木、赤黒木、ヒープと少しずつ難しくなっていく。
こういったワードからわかるように、アルゴリズムをかじっていれば一度は学んだことがあるものがほとんどではないか思う。木にデータを追加するときにどうノードを回転させるのか、などはどうしても時間が経つと忘れてしまうので定期的に復習する必要があると感じた。
ちなみに、読もうと思った理由のところに書いた「プログラミングとはつまるところアルゴリズムとデータ構造だ(意訳)」は今でもよくわからない。アルゴリズムとデータ構造を学べばプログラムで表現できるよ、ということを言っているのかもしれない。
この本で競プロやりたい熱が再燃した