ようやく最後までたどり着いたので忘れないように読書感想と学んだことをメモ

なぜ読もうと思ったのか

○アルゴリズムを知りたいと思った時に、アリ本がとっつきにくかった。
○Open Data Structures(みんなのデータ構造)がなに言ってるのかわからないくらい難しかった。
ちなみにこれは、無料公開されているので誰でも読むことができる。

Open Data Structures は Pat Morin 氏が執筆した、データ構造の入門書です。本プロジェクトでは、この本の和訳を作成し、PDF ファイルおよびそのソースコードを公開しています。

恥ずかしいことに、なにを言ってるのか全然わからないのと、とっつきにくすぎたので別の本を探すことに。ここで出会ったのがなっとくアルゴリズムで、絵が多いというのが特徴です。理解しやすそうだと思ったからこの本を読むことにしました。

内容について

各章は下記のような構成で、1~3章で基本的な説明を行っている。
4章以降で、1~3章の内容を踏まえて様々なアルゴリズムを説明していく構造になっている。

1章　二分探索　ビックオー記法
2章 配列とリンクリント
3章　再帰
4章　クイックソート
5章　ハッシュテーブル
6章　幅優先探索
7章　ダイクストラ法
8章　貪欲法(ナップザック問題と巡回セールスマン問題)
9章　動的計画法
10章　k近傍法
11章　これから先について(木、転置インデックス、フーリエ変換、並列アルゴリズム、SHAアルゴリズム)

良かったところ

●段階的に発展させてくれるから、挫折しなくてすむ。

実はこれまで三度くらい、三章まで読んでは途中でやめを繰り返していたが、サラッと見るだけだと理解して無くて、結局よくわからん→読むのをやめる→数カ月後に読むというループに陥っていた。
さすがに、本気を出して全部読もうと思ったので、Python2.7で書かれている問題例のコードを、Swiftで書き直して理解を深めてみるというのをやってみた。
おそらく本に乗っている実際に動かせるコードを全部Swiftで書き直したと思う。

実際手を動かしてみて思ったのだが、３章で使った内容を４章でも発展して使い、そして５章でさらに発展させるという形で段階的にわかるようになっている構成であることに気がついた。手を動かしてみないとわからないものである・・。

●練習問題がある
章の終わりに練習問題がある。コレの良いところは、一つに付き2~5分くらいで終わること。たくさん時間がかかると本章だけで、挫折しそうになるのに、問題がいい感じに軽いというところが乗り越えられるポイントだった

●気になっていたアルゴリズムが紹介されていた。
ナップザック問題や巡回セールスマン問題。名前は聞いたことあるけど、具体的にどうやって解くのか知らないという問題を絵付きで解き方が紹介されていてよかった。

●メモリの仕組みビックオー記法と配列とリンクリストの紹介
どうしたら早くなるかという話だけじゃなくて、そもそもどうして遅くなるのか、どうやって値が保存されているのかを扱っていてよかった。また、配列とリンクリストの違いを覚える時に「映画を見るために座席に座る」という例を持ち出し

５人の友人と連れ立って話題の映画を見に行くとしましょう。６人分の座席を見つけようとしますが、映画館は人でいっぱいです。６人がならんで座れる場所はありません。このような問題は配列でも発生することがあります。配列に対して10000個のスロットを確保しようとしているとしましょう。メモリには空きスロットが10000個ありますが、それらはまとまっていません。この場合、配列のスペースは確保できません。リンクリストは「別れて映画を見よう」と言うようなものです。メモリに空きスペースがあれば、リンクリストのスペースは確保できます。

このような感じで、思い出しやすい例が多くてよかった。

気がついたこと

●PythonからSwiftに書き直してみると、Swiftにはこの関数が無いんだなど普段意識しない気づきが多い。
Pythonのようにdequeというものは無いらしく、dequeってどう書くんだ・・と思い、調べたらswift-algorithm-clubに出会うことができた。素晴らしいリポジトリ。

●コードをただ見るだけだと脳内で再生できないので実際に手を動かしたほうが見に染み渡る
やっぱり流し読みをする癖があるようで、ちゃんと理解して進めていない感じがしていたが、コードを実際に書いてみるとびっくりするぐらい躓く。めちゃくちゃ時間がかかる・・・。
Xcodeのplaygroundの調子が悪かったので、Paizaを使って解いていた。
時間はかかってもいいからちゃんと動くようにするぞ・・・という気持ちでやった。
時間はかかったけど取り組んで良かったなってあとからじわじわ来るタイプの本だと思う。

●ハッシュテーブルについて
それまで辞書がなぜバラバラに入るのかという疑問すら持っていなかったのだけど、ハッシュテーブルだからか！とピンときた。

●youtubeのアルゴリズム動画を楽しめるようになった

見てて楽しい・・・　なんでこんな動き方になるのかわからんやつは多いけど。

●Qovoを使って、わかったこと、知ったこと新しい用語をメモりながら技術書を読むと挫折しなくてすみそう
ちょっとしか進めなくても、ここまでできたなって記録をとれるのがいい

まだわからなかったこと。
これから調べたり探求してみたいこと

●9章最長共通部分文字列
「hish」と入力したものから「fish」と「vista」どちらの単語を入力しようとしたのか動的計画法を用いて求めるという問題が、何度読んでもなんでそんなことが可能なのかさっぱりわからなかった・・・
まだこれを理解できるレベルに達していないということがわかった

●コサイン類似度

●時間計算量
どのシナリオがどの計算量なのかが、まだ腑に落ちていない
あと数学を忘れ去ってしまっているので、対数復習しないとなとなった

●ハッシュテーブルと占有率の話
これもう少し調べてみたい。言語によって違ったりするのかしら・・

まとめ

全然簡単じゃないし、なっとく！できたかというと怪しいところも多い。
絵にめちゃくちゃ助けてもらって挫折せずにすんだ。ありがとうわかりやすくて可愛い絵。(↓なっとくアルゴリズムより引用)

めっちゃ時間かかった・・・。これシュッて読める人すごいわ・・・・。
Swiftを書くことに対する姿勢が少し変わった気がする。いい本でした。

この本をきっかけで、ボゴソートというネタソートに出会えたのも大きい。