アルゴリ、データ構造をJavaでおさらいしてみました。
まさに「アルゴリズムとデータ構造」という授業でやった、リンクリスト、キュー、スタック、木構造、ソートといった内容をjavaで解説してくれています。
"Javaプログラマのためのアルゴリズムとデータ構造", 近藤嘉雪 著, SoftBank Creative
正直今更こんな復習が必要なのも情けないですが、データベースの仕組みを理解する上で、BTreeって実装できないよな。B+Treeは?B*Treeって何が違うんだったけ?となったので、今のうちに復習してみました。
頭のなかでぼんやりとイメージは出来たものの、改めてガッツリ写経して動かすことが出来て、だいぶ整理し直せた気がします。(気がするだけかい!?)
授業の時はC言語で習ったこともあり、タイプミスでいつまでも躓いたり、ポインタの理解が大変だったりといった感じでしたが、今回はアルゴリズムとオーダを意識しておさらいできたのでやってみる価値はあると思います。(←普通はそんなこともないか)
Javaで解説しているこの本では初歩的なオブジェクト思考も必要ないくらいで、基本的なアルゴリズムの実装を勉強できると思います。
おおまかな構成は以下のようになっています。
第1部: アルゴリズムの紹介や計算量の話
第2部: 基本的なデータ構造
連結・循環・双方向リスト、キュー、スタック、2分木の解説
第3部: 探索
ハッシュ法、2分探索木、平衡機(ALV木、B木)
第4部: 整列
単純な整列アルゴリズム(バブル・選択・挿入ソート)
比較によらないソート(ビンソート、分布数え上げソート、基数ソート)
第5部: 文字列の探索
第6部: 色々なアルゴリズム(バックトラック法、動的計画法)
全体的に解説が丁寧で、
・ アルゴリズムの概要が図付きで説明される
→ javaでの実装例
→ 更に実装例の細かい点の説明
と3段階に説明されているので、とてもわかり易いです。(ただ実装例見れば後の説明はいらないかも)
そして、これのためにこの本を手にとったといってもいい、3章にはB木の実装があり、15ページに渡った実装例が載っていたりします。(かなり丁寧にコメントがある)
ソートの説明もとても丁寧で、クイックソートの平均オーダはnlognで、最悪の場合n^2になってしまう、最悪のケースの解決法まで説明があるのが嬉しいです。
今後木構造やグラフ関連を、実装しつつ理解していくための足がかりとして、まずは良い復習になったと思います。
少々インターンや研究で間が空いてしまう気もしますが、こういったアルゴリズムの勉強と実装力の底上げも地道にしていこうと思います。