｢なっとく!アルゴリズム｣を読んだ件
きっかけ
僕の大学の先生がエンジニアになるならデータ構造とアルゴリズムが重要だと仰ってたので読んだ。エンジニアにとってアルゴリズムは切っても切り離せない関係らしい。授業で一度学んだが、あまり理解できてなかったため復習に読もうと思った。
内容について
2点紹介したいことがある。先述の技術とアルゴリズムの密接な関係の理解が深まった点と、僕のような初学者でも読みやすかった点だ。
技術とアルゴリズムの密接な関係について
本書を読んでみて、確かに技術の元がアルゴリズムになっていることがわかった。以下に本の章構成を記す。
【目次】
第1章 あれもこれもアルゴリズム
第2章 並べたり差し込んだり選んだり:ソート
第3章 同じ手順で何度でも:再帰
第4章 ちっちゃくしてから考えよう:クイックソート
第5章 関連付ければ話も早い:ハッシュテーブル
第6章 グラフを作れば見えてくる:幅優先探索
第7章 本からピアノへ物々交換大作戦:ダイクストラ法
第8章 問題は続くよどこまでも:貪欲法
第9章 ドロボーは計画的に:動的計画法
第10章 分類したら予測して:k近傍法
第11章 この先にはなにがあるの?
第12章 答え合わせ
前半はデータ構造、様々なアルゴリズム、アルゴリズムの評価方法について記述されている。
後半はより高度なアルゴリズムを学び、実用化されている技術に結びついてきた。特に9章と10章は身近な技術が出てきたため繋がりを感じやすかった。
9章: 動的計画法
動的計画法とは、問題を部分問題に分割しその解 (部分解) を使って全体の解を導く方法だ。
動的計画法は、問題を部分問題に分割できそれぞれ独立しているときに使える。
例えばgitのdiffコマンドは2つのファイルの違う部分を表示するコマンドだ。この文字列の比較に動的計画法が使われている。具体的には、文字列を分割して考え、その中で最長共通部分文字列をそれぞれ計算して全体の最長共通部分文字列を計算する。
考えるべき問題は全体の文字列についてで、それを計算するために文字列を分割している仕組みを学んだ。
10章: k近傍法
k近傍法は、あるデータがあったときに似ているk個のデータと比較することで元のデータを評価するアルゴリズムだ。NETFLIXのリコメンデーション機能は、他のユーザーの視聴記録とあなたの視聴記録を比較して関連するコンテンツを表示している。この機能にk近傍法が使われている。
簡単な例を挙げる。2つの評価軸x, yでユーザーの類似度を図る場合を考える。比較する2人のユーザーの値を(x, y), (x', y')とおき、類似度を距離dで測るとすると
である。dが小さいユーザーをk人選べば、類似したユーザーk人を選んだことになる。
基本はこのようなアルゴリズムだ。評価軸がn個になればルートの中の項数が増える。実際はデータ量を正しく測定するために正規化したり、cos類似度を使う。例えばあるユーザーは高い評価をつけがちで、低い評価をつけがちだったりするので、高い評価をつけがちなユーザーの星5よりも低い評価を付けがちなユーザーの星5の方が価値が高い。
中学の頃習った2点間の距離や、高校で習ったデータの分析が元になっているのを知り、学問が発展して技術に繋がっているのを実感できた。これを機に勉強に本腰をいれたい。
読みやすさについて
例えが秀逸でイメージしやすい。イラストも多く内容が入ってきやすかった。
最後に
章の後半にコードが書いてあるが、一通り読んだだけでまだ詳しく読み切れていない。アルゴリズムと実用化されている技術の繋がりを知れたので、一旦この本を読了することにした。僕のような初学者でもアルゴリズムの概要を知れる良書だった。
自分の文章が拙く分かりづらい部分もあるかも知れませんが、コメントでアドバイス頂ければ非常に嬉しく思います。
Discussion