データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。
日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。
内容
データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。
大学の教科書のように、正確性を優先したハードコアな内容。
アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深さ優先探索と幅優先探索を扱う。また、各データ構造の応用・発展や実世界との照合も各章の末尾に添えられている。
自分の読み方
すでに理解しているデータ構造は一部あったが、メモを取ったり写経したりを経て通読するのに14時間ほどかかった。
理解が及ばない部分や、訳者まえがきで重要性があまり高くないとされていた一部（スケープゴート木とかトライ木とか）は読んだものの完全理解する前に先へ進んだ*1。
練習問題は全部やるとかなりハードなので1周目では問題を眺めつつ解法を想像するぐらいにして、2周目に復習としてやるぐらいが良いと思った。
数学
計算量の解析や定理の証明部分はけっこうハードコアで高校数学を復習しないとかなり厳しそうであった。最初は数式と向き合っていたがやりたかったデータ構造の学習から逸れそうなのでほどほどに読み飛ばすことにした。
苦しんだ一方、データ構造とそれを支える数学的背景の理解のために自分が数学のどの分野を学習すればよいのかが見えてよかった。特に確率論が弱い。
言語
本書に掲載されているコードはすべてC++だが、他言語でのプログラミング経験者なら書籍に掲載されているコードがC++であることは問題ない。
(2020-05-10 22:56 JST 追記) 訳者の方から他言語の実装や擬似コードもあるとのご指摘いただきました。ありがとうございます！
C++をメインの言語として利用していない自分にとってはむしろ、C++で書かれたアルゴリズムを慣れた言語に落とし込むことでより頭を使う写経になって良かった。
補助教材
本書は図とコードを豊富に載せているが、それでも挙動がピンと来ない場合はデータ構造やアルゴリズムの名前で検索したり、以下のサイトでアニメーションを見て視覚的に理解することに努めた。
また、同時期に視聴していたCourseraのアルゴリズム講座で同種のデータ構造*2に出くわしたり、Courseraの課題を解く際に本書を参照したり、相互に補完しあって理解を深めることができた。同講座に関する感想は以下の記事にまとめた。
印象に残ったところ
印象に残ったところの感想を少しだけおさらい。
「2章 配列を使ったリスト」「3章 連結リスト」
さすがにStackとかQueueとか理解しているだろと思って読み始めたところ、自分が理解しているのは抽象・インタフェースとしてのデータ構造とその使い方であって、内部実装まではイメージできていなかったことがわかって序盤から引き込まれた。
同じインタフェースでも内部実装を変えることで処理時間やメモリ効率が変わるのは当たり前のことなのだがそのプリミティブな実装を複数並べて比較することができて面白い。
「4章 スキップリスト」「5章 ハッシュテーブル」
スキップリスト、ハッシュテーブル、Treap、クイックソート等々…ランダム性を扱うデータ構造やアルゴリズムのかっこ良さが心で理解できた。
Skip Listやランダム二分探索木などを学んで乱択に感動しているので『数学ガール 乱択アルゴリズム』読み進めるぞ
— ohbarye (@ohbarye) 2020年4月24日
「6章 二分木」「7章 ランダム二分探索木」「9章 赤黒木」「10章 ヒープ」
木が多すぎてもはや森。
赤黒木の代償として実装が複雑という話が出てきており、これはSedgewick先生がCourseraの講座でも言っていたことを思い出した。特に2008年のLeft-Leaning Red Black Treeの発表以前、とあるデータベースプロバイダが赤黒木の削除の実装を誤ったために障害を起こしたという話。（木の高さを常に一定に保つことが保証されていないHibbard deletionを採用したので木の高さが高くなりすぎ、再構築のためにシステムダウンするほどだった）
「14章 外部メモリの探索」
B treeとデータベースの話がC言語でSQLiteのクローンを作るチュートリアルやった - valid,invalidで学んだ内容とリンクしており、知識の点が線になった感覚があってよかった。
感想
業務にて行き当たりばったりでデータ構造を学んできた身からすると、このように正確性を重視しつつ体系立てて基礎を学べる一冊があるのはありがたい。
この本で扱うのはシンプルなもののみだが、実世界のソフトウェアの骨子はシンプルなデータ構造の組み合わせでできているから、本書の内容を理解することは良いソフトウェアエンジニアになるために有用だ（本書の訳者まえがきより）…という主張もグッときた。
自分同様にデータ構造の基礎を学習したい人には無条件でおすすめする。
