【技術書まとめ】なっとく! アルゴリズム

アルゴリズムとデータ構造について学ぼうと思った。
1冊目。


# 1：あれもこれもアルゴリズム

- 二分探索
    - 0~100を1つ思い浮かべてもらい最短で当てる
        - 半分ずつ除外する
        - 240000語ある場合
            - 1から順番だと240000ステップ -> 18ステップ
                - $n$ -> $log_2 n$
    - ソートされていないとダメ

    ```ts:二分探索
    function binarySearch<T>(list: T[], item: T): number | null {
        let low: number = 0;
        let hight: number = list.length - 1;
    
        while (low <= hight) {
            let mid: number = Math.floor((low + hight) / 2);
            let guess: T = list[mid];
            if (guess === item) {
                return mid;
            }
            if (guess > item) {
                hight = mid - 1;
            }
            if (guess < item) {
                low = mid + 1
            }
        }
    
        return null;
    }
    
    const myList = [1, 3, 5, 7, 9];
    
    console.log(binarySearch(myList, 3));　// 1
    console.log(binarySearch(myList, -1)); // null
    ```
- 40億個の場合は40億個回推測する：線形時間（linear time）
    - $O(n)$
- 二分探索は40億個で32回推測：対数時間（logarithmic time）
    - $O(log_n)$
- ビッグオー記法
    - 演算の個数を比較できる
        - 16個のマスを描く
            - ひとマスずつ描く
                - 16回描く
                    - $O(n)$
            - 折りたたむ
                - 4回折りたたんでマスを描く
                    - $O(log_n)$
                    - 加速していく
    - 最悪の場合の時間計算量を定める
        - 単純探索は$O(1)$ではなく$O(n)$
            - 最悪でも$O(n)$よりは時間がかからない保証のようなもの
    - 高速順
        - アルゴリズムの速度は秒速ではなく演算の実行回数の増加で表す
            - 入力サイズの増加で計算時間がどれだけのペースで上昇するかわかる
        - 対数時間$O(log_n)$ < 線形時間$O(n)$ < $O(n log_n)$ < $O(n^2)$ < $O(n!)$
            - $O(log n)$は検索対象となるリストが大きくなるにつれて加速していく
        - ![スクリーンショット 2023-06-30 9.05.09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/abad0765-15ee-49b8-6308-60d4d93963ec.png)
    - 巡回セールスマン
        - 5都市だと120回、6都市だと720回と指数関数時間(factorial time）として伸びていく
            - 100都市になると太陽が崩壊する


# 2：並べたり差し込んだり選んだり：ソート

- メモリは、引き出しがついた収納スペース
- TODOリストを作りたい
    - 配列でやると
        - すべての要素が隣り合わせに格納される
        - 配列で3つスペースを確保したが、次のスペースが他の誰かに使われている
            - 移動しないといけない
                - 配列に追加があるたびに移動する必要が出てくる
                    - ムダ
                - 最初から10個スロットを確保しておく
                    - 移動しなくてもよくなるがムダが生まれる
                        - 映画を観るときに、「誰か来るかもしれないから10席取っておこう」
        - 配列は繋がっているので、要素をランダムに読み取りたい場合に適する
            - リンクリストだと順番にアドレスを取得していかないといけないから
            - 配列は読み取りが$O(1)$で高速で、挿入が$O(n)$で低速
            - **配列はランダムアクセスや検索が得意**
                - 二分探索で必要
    - リンクリストでやると
        - メモリ内のどこにでも配置できる
            - それぞれ次の要素のアドレスを格納する、宝探しのようなもの
                - 「分かれて映画を観よう」
            - 1つずつ読み取っていかないといけないというデメリット$O(n)$
                - 「次へが10個ある記事」
                - シーケンシャルアクセス（sequesntial access）、逐次アクセス
            - 要素を途中で挿入したい場合は、リンクリストが適している
                - ![スクリーンショット 2023-07-05 21.29.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/183c6269-bcaf-b6af-f058-ba1d9a682614.png)
                - 1つ前の要素が指しているものを変更すればいいだけだから
                    - 配列だと以降の要素を全て後方に移動する必要がある
                    - 削除も同じで簡単
                - **リンクリストは挿入、削除が得意**
- たくさんの曲の中で再生数が多いものから順に並べる
    - 全部調べてもっとも再生数が多いものを1番目に持ってくる -> 繰り返していく
        - $O(n^2)$
            - そこまで高速ではない
        - これを**選択ソート（Selection Sort）** と呼ぶ


# 3：同じ手順で何度でも：再帰

- 再帰が使われるのは、それによりソリューションがより明確になる場合
    - パフォーマンス上のメリットはない
- 再帰関数を書くときには、再帰がいつ終了するのかを指定する必要がある
    - すべての再帰は基本ケースと再帰ケースの2つ部分で構成される
- スタック
    - TODOの付箋が積み重なったもの
        - プッシュ：新しいアイテムを追加
        - ポップ：一番上のアイテムを取り出して読み取る
    - コールスタック
        - greet()　の中にgreet2()とbye()がある
            - 関数ごとにメモリを1箱用意する
            - greet()スタックの上にgreet2()スタックが積まれる
            - greet2()スタックが実行されると箱がポップされる
            - greet()スタックに制御が戻る（greet()は中断された不完全な状態だった）
            - bye()がgreet()スタックの上に積まれる
            - bye()が実行されたらポップされる
            - greet()スタックに制御が戻る
- 終わらない再帰を書いた場合
    - コールスタックを使い果たしたとき、スタックオーバーフローエラーで終了する


# 4：ちっちゃくしてから考えよう：クイックソート

- 分割統治（Divide and Conquer: D&C）
    1. できるだけシンプルな基本ケースを特定する
        - リストの場合は、だいたい空配列か、要素が1つの配列になる
    1. 基本ケースになるまで問題を分割（縮小）していく
- 1680m x 640mの農地を正方形の区画にできるだけ大きく均等に分割したい
    - ![スクリーンショット 2023-07-05 10.52.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/d51aaa69-aebe-9e45-336c-53d1dc8ed4f2.png)
    - 640mの正方形*2で640 x 400の土地が余る
        - 640 x 400の農地の分割を考えればいい
            - 問題が縮小された
                - 再帰で繰り返すと、最後に80 x 80の正方形で割り切れる
                    - 最初の農地で使うことができる最も大きな区画は80m x 80mとなる（基本ケース）
- 再帰を使って[2, 4, 6]をすべて足して合計を返す
    - ![スクリーンショット 2023-07-05 14.34.01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/b2e45f48-5361-ff8f-d8f4-203f1e83aa5a.png)
    - 最大限分割された状態でかつ、自信を持って答えを決定できる状況を基底条件とする
        - いつ再帰から抜け出すか
            - まずはこれを決める
- クイックソート
    1. 配列の要素が2より少ない（0 or 1）の時を基底ケースとして、その場合はソートが必要ないため配列の中身をそのまま返す。
    1. pivotを選んで、その他をlessとgreaterに分けてパーティショニングする。
    1. lessとgreaterが複数であれば、基底ケースに達するまで再起的に[2]を行う。
    1. 基底ケースで戻り値が決まり、コールスタックの上から順に戻り値が決まっていく。
    1. 最後にソートされたlessとgreaterが決まり、pivotを中央として配列がconcatされる。
    1. ソートされた配列が完成する
- ビッグオー記法
    - ![スクリーンショット 2023-07-05 17.53.27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/6a14c5d4-8bc8-e842-60c7-4e553205f550.png)
- マージソートとクイックソート
    - ビッグオー記法の$O(n)$は、実際には何らかの一定の時間cをかけた$c*n$となる
        - 処理する数が大きくなると定数部分はあまり関係なくなる
    - クイックソートはピポットの選択で最悪のケースと平均的なケースに分かれる
        - ![スクリーンショット 2023-07-06 9.12.45.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/3350ecec-0f8b-f1f6-8bb2-1dacab434fed.png)
            - 最悪のケースは8個の要素すべてにアクセスしている
                - $O(n)$列 * $O(n)$段
        - ![スクリーンショット 2023-07-06 9.12.59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/e64081ed-a426-a359-35d3-d6ecd438fdec.png)
            - 最良のケースはピボットする要素を常にランダムに選ぶ方法
                - $O(n)$列 * $O(log_n)$段
                - これが平均的なケースとなる


# 5：関連付けると話も早い：ハッシュテーブル

- アルファベット順に並んでいない価格表から、「リンゴ」の値段を探す
    - 単純探索：$O(n)$
    - 二分探索：$O(log_n)$
    - これを定数時間$O(1)$でやりたい
        - 相棒のマギーはすぐに答えてくれる
            - ハッシュテーブルというデータ構造
        - ![スクリーンショット 2023-07-11 9.26.51.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/90f82a3f-9e37-95ad-6775-440c8b165a14.png)
        - 配列から要素を取り出すのも定数じかん
- ハッシュ関数
    - 一貫して、名前を同じインデックスにマッピングする
    - 異なる文字列を異なるインデックスにマッピングする
    - 配列の大きさを把握しており、有効なインデックスだけを返す
- ハッシュテーブルが最適なもの
    - あるものから別のものへマッピングする
        - `http://adit.io` -> `173.255.248.55`に変換する
            - DNS解決はハッシュテーブルが最適
    - 重複を取り除く
    - 何かを調べる
        - キャッシュされているデータがあるかどうか
- 衝突
    - 同じスロットに2つ以上のキーがマッピングされてしまった
        - そのスロットでリンクリストを開始する
            - できるだけ均等にマッピングしないと検索効率が落ちる
                - よいハッシュ関数が必要
- パフォーマンス
    - ![スクリーンショット 2023-07-11 9.29.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/58cf9899-df02-8ca6-09bd-0bd789e1382a.png)
        - ハッシュテーブルは最悪なケースになるとすべて$O(n)$となる
        - 平均的ケース
            - 検索では配列と同じくらい高速
            - 挿入と削除に関してはリンクリストと同じくらい高速
    - 占有率0.7を超えた時点でリサイズしたとしても、平均するとハッシュテーブルの計算時間は$O(1)$となる


# 6：グラフを作れば見えてくる：幅優先探索

- 幅優先探索（breadth-first search)
    - 幅は同じ深さのノードを表す
        - すべて探索してから次に進む
    - 「Xまでの最短経路は何か」に答える
        - 最短経路問題
- グラフとは
    - ノードと辺でモデル化したもの
        - 「AlexはRamaに借金がある」
        - 直接接続できるノードは隣接と呼ぶ
- 幅優先探索
    - 「友人の中にマンゴー販売者がいるか、Facebookで友人の友人まで見つかるまで辿っていく」
        - 一次つながり、二次つながりと辿っていく
    - キュー
        - バス停の列と同じ
            - エンキューは列に並ぶこと、デキューは先頭の人がバスに入ること
                - 先入れ先出し：FIFO（First in, First out)
                    - スタックは、後入れ先出し：LIFO（Last in, First out）
                    - ![スクリーンショット 2023-07-13 9.06.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/2b877c2c-1328-b126-3e33-2b5f52299bd7.png)
    - 最後のノードには別のノードへ向かう矢印がない
        - 有向グラフ（directed graph）
            - AnujはBobの隣接ノードだが、BobはAnujの隣接ノードではない
            - 矢印を持たないものは無向グラフ
    - アルゴリズムの実装
        - ![スクリーンショット 2023-07-13 9.24.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/282504/525ab371-aaed-16d8-112e-b4ff285747d2.png)
        - ```ts
            interface Graph<T> {
                [key: string]: T[]
            }
            
            const personIsSeller = (name: string): boolean => {
                return name.endsWith('m');
            }
            
            const graph: Graph<string> = {};
            graph.you = ['alice', 'bob', 'claire'];
            graph.bob = ['anuj', 'peggy'];
            graph.alice = ['peggy'];
            graph.claire = ['thom', 'jonny'];
            graph.anuj = [];
            graph.peggy = [];
            graph.thom = [];
            graph.jonny = [];
            
            const search = (name: string): boolean => {
                let searchQueue = graph[name];
            
                const searched: string[] = [];
            
                while(searchQueue.length > 0) {
                    const person = searchQueue.shift();
                    if (!person) {
                        return false;
                    }
            
                    if (!searched.includes(person)) {
                        if (personIsSeller(person)) {
                            console.log(`${person} is mango seller!!! WOW!!`);
                            return true;
                        } else {
                            searchQueue = searchQueue.concat(graph[person]);
                            searched.push(person)
                        }
                    }
                }
            
                return false;
            }
            
            search('you');
- 時間計算量
    - 各辺を辿るので少なくとも$O(辺の個数)$となる
        - すべての人に実行すると$O(人数)時間$かかる
            - 幅優先探索にかかる時間は、$O(人数 + 辺の個数)$であり、$O(V+E)$と書ける
                - Vは頂点の個数、Eは辺の個数
- 木は常にグラフだが、グラフは木である場合とそうでない場合がある


# 7：本からピアノへ物々交換大作戦：ダイクストラ法

- ダイクストラ法
    - 「最速」の経路を見つけられる
        - 近道を見つける方法
        - 重み付きグラフだから
            - 重み付きでないときは幅優先探索を使う
        - 負の重みが付いていると使えない
    - ステップ
        1. 「最もコストが低い」ノードを探す
        1. このノードから隣接ノードへの経路に、よりコストの低い経路があるか調べる。ある場合はノードのコストを更新する
        1. グラフ内のノードごとに同じ作業を繰り返す
        1. 最終経路を割り出す
- 閉路
    - ループとなる区間
        - 無向グラフは閉路
    - ダイクストラ法がうまくいくのは有向無閉路グラフ（firected acyclic graph）だけ
- 辺に負の重みが付いている場合、ダイクストラ法は使えない
    - 負の重みが存在する場合、後から更にコストが小さくなる経路が現れる可能性がある
        - すでに処理済みとしたノードが再更新されてしまう
            - 正しく計算できなくなる
                - ベルマンフォード法を使う
- ダイクストラ法のアルゴリズム
    - 処理するノードがなくなるまでの間
    - STARTに最も近いノードを取得
    - その隣接ノードのコストを更新
    - 隣接ノードのいずれかのコストが更新された場合は、親も更新
    - このノードを処理済みとして指定


# 8：問題は続くよどこまでも：貪欲法

- アルゴリズムによる高速な解決法がない問題（NP完全問題）に取り組む方法
    - 高速なアルゴリズムを見つけ出そうとして時間を無駄にしないようにする
        - 近似アルゴリズムで近似解をすばやく見つける
            - シンプルな問題解決方法である貪欲法
- 貪欲法
    - 最初に全体の設計をせず目の前の最適解を選んでいく
        - 局所的最適化の積み重ね
            - 書くのが簡単ですばやく実行できるので、よい近似アルゴリズムとなる
    - 各ステップで局所的最適解を選んでいく方法
        - 時間割決め
            - 最初は最も早く終わる授業を選び（美術）、次は美術より後から始まり最も早く終わる授業を選ぶ
                - これを繰り返す
        - ナップザック問題
            - 高価なものからバッグに詰める
                - 最適解ではないが近い解は求められる
        - 集合カバー問題
            - 放送局をできるだけ少なくしたい
                - 部分集合の洗い出しに$O(2^n)$かかるため、増えると十分な速さで解決できなくなる
                - 貪欲法で近似を出せる
                    - 貪欲法は$O(n^2)$
    - クイックソートと幅優先探索は貪欲法
- NP完全問題
    - 巡回セールスマン問題
        - 階乗関数となる
            - 近似値を求めるには？
                - 出発点から最も近い都市を選んでいく
                    - 最も近いもので局所的にFIXしていく
    - 集合カバー問題
    - NP完全の匂いがするものは？
        - アイテム数が増えるとかなり低速になるもの
        - 「Xのすべての組み合わせ」
        - 問題を分割できないため、Xの「考えられる限りのバージョン」を計算する必要がある
        - 巡回セールスマンのように問題がシーケンスに関係していて解くのが難しい
        - ラジオ放送局のように問題が集合に関係していて解くのが難しい
        - 問題を集合カバー問題や巡回セールスマン問題として言い換えられるならNP完全問題


# 9：ドロボーは計画的に：動的計画法

- 動的計画法
    - 　問題を小さく分解し、それらの部分問題を先に解くことで難しい問題を解く手法
        - 　制約を前提として何かを最適化するときに役立つ
            - 　何かを最大化して解く: 共通文字の数を探索する
- 　ナップザック問題
    - 　単純解
        - 　考えられうる限りの組み合わせを試す
            - 　時間がかかりすぎる（$O(2^n)$）：品物が32個なら集合は40億個
    - 　近似解なら貪欲法
    - 　最適解は？
        - 　動的計画法
            - 　4ポンドのナップザック問題を解くために1ポンド、2ポンドと解いていく
                - 　スペースが余った場合に、その部分問題に対する解が使える：1ポンド余った場合の最適解はギター$1500を入れる
            - 　「行のアイテムを選んで、選択しない場合は既存の解が最適解となり、選択する場合は余りを既知の部分解で解く」ことを繰り返す
    - 相互に依存する項目があると動的計画法ではうまくいかない
        - パリに着くとルーブル美術館の使用日数が変化する
    - ナップザックが完全に埋まらない最適解もある
        - ダイヤモンドを入れたが残りが埋められない
- どこで使われているか
    - diff
        - 共通文字を探索して差分を明らかにする


# 10：分類したら予測して：k近傍法

- k近傍法（neighbor algorithm）
    - k個の近傍を調べる方法
        - 特徴量を抽出してアイテムを比較可能な数字のリストに変換する
    - 具体例
        - オレンジとグレープフルーツどちらに近いか考えて分類する
            - OCRも新しい文字の直線、点、曲線を計測する
    - 正しい特徴量を選ぶことが重要
        - 映画好きに猫の絵を選ばせたり、トイストーリー123だけを選ばせても、映画の好みはわからない


# 11：この先にはなにがあるの？

- 木（ツリー）
    - Btree
    - 赤黒木
    - ヒープ
    - スプレー木
- 転置インデックス
    - テキスト内の単語をキーとして、単語と関連するテキストを持つ逆引き目次
- フーリエ変換
    - いろんなところで使われている
    - 曲を周波数ごとに分解してくれる
        - MP3, JPGなどの圧縮フォーマットで使われる
- 並列アルゴリズム
    - パフォーマンスやスケーラビリティを向上する並列処理で使われる
        - 複数CPUでの処理
        - ロードバランシング
- MapReduce
    - 分散アルゴリズム
        - Apache Hadoop
- ブルームフィルタとHyperLogLog
    - 非常に大きな集合がある状態
        - 新しいアイテムがその集合に属しているかどうか考える
            - 良くないURLを検出する
    - ハッシュテーブルは$O(1)$だが、膨大な量だと工夫が必要になる
    - ブルームフィルタ
        - 確率的データ構造（probabilistic data structure）
            - 間違っている可能性があるものの、おそらく正しい答えを提供する
                - 正確な答えが必要でない場合にGOOD
                    - このサイトは注意してね、は間違っていても問題ない
    - HyperLogLog
        - 集合に含まれている一位な要素の個数を概算する
            - 近似的な解で十分な場合
- SHA
    - ハッシュ関数
        - 十分な分散を実現できるのでハッシュテーブルに使える
        - 一方向しか変換できないかつユニークなのでファイルやパスワードの同一性確認に使える
- LSハッシュ
    - ハッシュ関数は類似するデータでもハッシュは近い値にならない
        - Simhashは似たデータは近い値になる
            - 同じようなアイテムの重複を検出できる
- ディフィー・ヘルマン鍵変換
    - 自分の秘密aを誰にも（相手にも）知らせないまま、AさんはBさんと共有の鍵を持てる
    - DF法の後継がRSA
- 線形計画法（linear programming）
    - 筆者が知る中で最もすばらしいアルゴリズム
    - 何らかの制約を前提として、何かを最大化するために使われる
        - 11メートルの生地と20個のボタンがあるが、何枚のシャツと何個のカバンを作れば一番儲かるか