readプライベートで色々あったものの、合間をぬってアルゴリズムの勉強をちょいちょいやっていた。プライベートでの色々は感情的にも状況的にも思考的にも大きく揺り動かされることが多かったのでいずれ時間を作って振り返りたい。(S.S.スキーナ)での気になっていたアルゴリズムを実装し終えた。関連して計算理論の基礎、オンラインアルゴリズムとストリームアルゴリズム、純粋関数型データ構造も読んた。やったこと以下のアルゴリズムをGoで実装した。データ構造キューデックRB木Union-Find文字列検索Aho-CorasickDP(Levenshtein)Rabin-Karp最小スパニング木PrimKruskal最短経路問題A*DijkstraViterbi素数Eratostheresマッチング2部マッチングGale-Shapley最大流Edmonds-Karp連結点(articulation)DFS,lowlink振り返り綺麗にとかまったく考えず、とにかく動かすのを目指した。一回書いてみると慣れて心理的な抵抗が軽減される。問題を考えるのが楽になった。これは頻繁に利用する基本的なアイディアが身についてきたということだと思う。あと必要に応じて書けるという自信がついたのも大きい。ここからは、テストと同じで類題を解いたり自分で整理して体系化したり丁寧に仕上げてみるとか効果が大きい気がする。書いている時に感じたのだが、特にグラフアルゴリズムでは中間的に利用するデータ構造をまとめてると楽になる。これは問題の入力に対応するグラフと別にする。すごい当たり前のことなんだけどアルゴリズムで利用する中間データに専用の型を与える。Goではサブルーチンをレシーバ関数にする。アルゴリズム設計マニュアルで学んだ基本的なアプローチを列挙する。上/下」を中心に置いた勉強はこれで止める。いままでの基礎練習と読書を踏まえ、理論方面の勉強について3つの方向を広げるつもりでいる。代数の復習とりあえず計算困難問題に対するアルゴリズム理論を読み始めた。近似アルゴリズムを買ったので続いて読む。純粋関数型データ構造も合間を見て読み返す。代数は楽しいけど後回しにする。(正直、まぁ基礎は組んでるし必要に応じて調べ直せばまぁ対処できるよねって感覚がある)実装方面ではAtCoderの過去問も再開する。Elixirで何かライブラリを作ってみようかと考えている。これはElixirはアルゴリズム系ライブラリが貧弱なので隙間が多いということと、業務で使っているため。