「なっとく! アルゴリズム」を読んだ
- 作者: アディティア・Y・バーガバ,株式会社クイープ
- 出版社/メーカー: 翔泳社
- 発売日: 2017/02/01
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
目次
- 目次
- 全体的な感想
- 気になった箇所のメモ
- 今後やること
全体的な感想
- アルゴリズムの入門者向け。苦手意識を克服するには良い。
- これ一冊で詳しくなれる訳ではないが、図解で具体的も詳しく記載されていて、イメージしやすいので良い。
- 今まで曖昧だったところが整理できた。
- 一番の気づきは、データ構造とアルゴリズムはコンピュータサイエンスの全ての基礎であること。
気になった箇所のメモ
第1章 あれもこれもアルゴリズム
巡回セールスマン問題
セールスマンが複数の都市をすべて最短距離で回る方法を求める方法。
単純そうに見えて、O(n!)の時間がかかる。
近似的に課題を置き換えて解決するしかないそう。
巡回セールスマン問題 - Wikipedia
第2章 並べたり差し込んだり選んだり：ソート
配列とリンクリスト
- 配列は、連続したメモリに格納する必要があるために、挿入や削除のパフォーマンスが悪い。
- 言語によっては配列の長さを事前に定義する必要があるのはこのためかと思った。
- 一方、リンクリストは連続していないメモリに格納するために、ランダムアクセスするのにO(n)かかりパフォーマンスが悪い。
| 配列 | リンクリスト | |
|---|---|---|
| 読み取り | O(1) | O(n) |
| 挿入 | O(n) | O(1) |
第3章 同じ手順で何度でも：再帰
while vs recursion
言語仕様によっては再帰関数を呼ぶとメモリ上にコールスタックが中断した状態で残り続けるために、パフォーマンスが良くない場合がある。
その場合は、whileに置き換えた方が良い場合がある。
もしくは、末尾再帰を用いる。（ただし一部の言語のみサポート）
# 再起 def fact(x) return 1 if x == 0 fact(x - 1) * x end # 末尾再起 def fact_tail_call(x, m = 1) return m if x == 0 fact_tail_call(x - 1, x * m) end
第4章 ちっちゃくしてから考えよう：クイックソート
分割統治
脱線するが、Haskellなどの関数型プログラミング言語にはloopがないらしい。
そのため、再起を使わないといけない。
sum [] = 0 sum (x:xs) = x + (sum xs)
第5章 関連付ければ話も早い：ハッシュテーブル
| ハッシュテーブル（平均） | ハッシュテーブル（最悪） | 配列 | リンクリスト | |
|---|---|---|---|---|
| 検索 | O(1) | O(n) | O(1) | O(n) |
| 挿入 | O(1) | O(n) | O(n) | O(1) |
| 削除 | O(1) | O(n) | O(n) | O(1) |
上表のように、ハッシュテーブルは配列とリンクリストの長所を兼ね揃えている。
ハッシュテーブルのパフォーマンスを上げるには、次の2つが重要
* 占有率を下げること
* 占有率 = ハッシュテーブルの要素の個数 / スロットの総数
* 要素数が増えると、ハッシュテーブルをリサイズする必要がある。
* 大体占有率が0.7を超えたらリサイズする目安
* よいハッシュ関数
第6章 グラフを作れば見えてくる：幅優先探索
グラフ：ノードと辺で構成されるモデルのこと。
幅優先探索：
* ノードAからノードBへの経路はあるか
* ノードAからノードBへの最短経路は何か
探索する際には、追加された順に重複なく調べる。
第7章 本からピアノへ物々交換大作戦：ダイクストラ法
ダイクストラ法
- 「最もコストが低い」ノードを探す。
- このノードの隣接ノードのコストを更新する。
- グラフ内のノードごとに同じ作業を繰り返す。
- 最短経路を割り出す。
有向無閉路グラフのみ算出可能。
負の重みを持つ辺があると、対応できない。
第8章 問題は続くよどこまでも：貪欲法
貪欲法
現状で選択可能で、最も解の状態に近づける選択を重ねて近似解を求める手法。
トラックに重い荷物から先に詰めていくようなイメージ。
NP完全
全ケースを計算しないと、厳密解を求められないこと。
ex. 巡回セールスマン問題や集合カバー問題など
第9章 ドロボーは計画的に：動的計画法
動的計画法
ある制約が与えられた問題を部分問題に切り分けて、問題を解く。
第10章 分類したら予測して：ｋ近傍法
ｋ近傍法
ある集合を特徴量によってグラフ化して、ある要素のk個の距離の近い要素からその要素を評価する手法。
レコメンドシステムでユーザの特徴を定量化して、レコメンドするなど。
