深掘り– category –
**本線を一周した人向け。** roadmap.sh のコースを1つ選んで、その中を細かく潰していく記録。**順路ではありません。** 必要になったコースだけ読んでください。
-
コンピュータ科学 深掘り
ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た
3件の配列を並べ替えただけで 1, 10, 2 が返ってきたとき、私は自分のコードのどこかにバグがあると思って30分探しました。バグはありませんでした。この記事では VM の中に ~/cslab/sort を作り、バブル・選択・挿入・マージ・クイック・ヒープの6つを自分で書きます。同じ4種類のデータで、時間だけでなく比較回数と書き込み回数を数えて1枚の表にします。すでに並んでいるデータで自作クイックソートを走らせて Maximum call stack size exceeded を出し、軸の選び方を変えて直るところまでやります。同点データを並べ替えて「安定」が何のことかを出力で見て、最後に V8 の sort と全部を測り比べて ~/cslab を消します。 -
コンピュータ科学 深掘り
二分探索木と3つの巡回 — 木にしたのに一直線になる
二分探索木は「探索が O(log n) になるデータ構造」だと覚えていました。実際に 1,2,3,... を順に入れてみたら、木の高さが 39999 になり、1件探すのに平均 20000 回比較していました。木ではなく、右に伸びた連結リストになっていたのです。この記事では VM の中に ~/cslab/tree を作り、insert / search / min / max / delete を自分で書き、削除の3パターンを図で確かめます。3つの巡回を並べて in-order だけがソート済みで出てくることを見て、幅優先はキューで書きます。最後に並んだデータを入れて高さと探索時間を実測し、再帰版の巡回を 20000 件で落として、明示的なスタックのループ版に書き換えて全部消します。 -
コンピュータ科学 深掘り
グラフとBFS・DFS — 循環参照で探索が止まらない
グラフ理論は数学の話ではなく、npm の依存関係も Git の履歴も Docker Compose の depends_on も全部グラフです。木と違って輪ができるので、訪問済みを管理しないと探索が止まりません。隣接リストと隣接行列を両方書いてメモリを実測し、BFS と DFS を書いて訪問順と経路の長さを並べて見ます。輪のあるグラフで visited を外すと本当に止まらないことを、回数の上限を付けて安全に再現します。最後に循環検出・トポロジカルソート・連結成分・全域木まで、実際に動くコードで確かめます。 -
コンピュータ科学 深掘り
PとNP・NP完全 — 答え合わせは一瞬なのに解けない
シフト表を自動で組む機能が、いくら速くしても終わらなかった。原因はコードではなく問題のほうでした。巡回セールスマンを Node.js で総当たりして、n を1増やすたびに時間が n 倍になる壁を実測します。「答え合わせは一瞬なのに、探すのは無理」という非対称を見てから、P・NP・NP完全・NP困難を1枚の表で整理します。ナップサック、ハミルトン閉路、最長経路、グラフ彩色を実際に走らせ、オイラー路や最短経路が一瞬で終わるのと並べて比べます。最後に現場の逃げ道4つ(貪欲・2-opt・問題を小さくする・時間で打ち切る)を実装して、最適解・所要時間・実装の手間を表にします。 -
コンピュータ科学 深掘り
プロセスとスレッドと競合状態 — たまにだけ数が合わない
4つのワーカーで100万回ずつ足すと、合計は400万になりません。走らせるたびに違う数が出て、しかも5回に1回くらいは正解が出ます。これが「たまにしか再現しないバグ」の正体です。SharedArrayBuffer で実際に起こして、Atomics.add で直します。さらに Atomics.wait で小さなミューテックスとセマフォを自作し、ロックの順番を逆にしてデッドロックをタイムアウト付きで再現します。最後にスケジューリングと仮想メモリを、vmstat・nice・free で実際に確かめます。 -
コンピュータ科学 深掘り
再帰とメモ化 — メモを1行足したら一瞬で終わった
フィボナッチを素直に書いたら fib(45) が返ってきませんでした。原因はアルゴリズムではなく、同じ引数を何千万回も計算し直していたことです。呼び出し回数を実際に数え、Map に覚えさせる1行を足して fib(90) が 0.04ms で返るところまでを実測します。あわせて末尾再帰が JavaScript では救いにならないことをスタックを溢れさせて確認し、N-Queen とナイトの巡回で「置く・進む・戻る」を書き、ナップサックを総当たり・メモ化再帰・動的計画法の3通りで測って並べます。最後に順列と組み合わせを列挙し、誕生日のパラドックスをシミュレーションしてハッシュの衝突に繋げます。 -
コンピュータ科学 深掘り
最短経路アルゴリズム — ダイクストラは負の重みで壊れる
前の回で「重みが全部同じなら BFS が最短を出す」と分かった。では区間ごとに所要時間が違う路線図では? 10駅の路線図を作り、BFS とダイクストラの答えを同じグラフで並べて、乗り換え1回・40分と乗り換え4回・21分が別物であることを確かめる。次に負の重みを1本だけ入れて、ダイクストラがエラーも出さずに静かに間違えるところを実際に出力する。ベルマン・フォードで正しい答えを出し、負の閉路の検出まで実装して、為替の裁定取引が同じ問題だと確かめる。最後に格子迷路で A* とダイクストラの調べたマス数を数え、最小全域木をクラスカル法とプリム法の両方で解く。 -
コンピュータ科学 深掘り
文字列探索とKMP — grepは1文字ずつ見ていない
indexOf があるのに、なぜ探索アルゴリズムを知るのか。素朴な探索・KMP・Boyer-Moore・Rabin-Karp を全部自分で書いて、比較回数と時間を実測します。最悪ケースを自分で作って素朴な探索を19,990,100回まで膨らませ、KMPで33分の1にします。Boyer-Moore がパターンを長くするほど速くなることを、比較回数が半分ずつ減るところまで数えます。ハフマン符号は英文4MBの出現頻度から符号表を作り、gzip の実測圧縮率と並べます。最後に接尾辞配列で「何回引いたら作る価値があるか」の交差点を出します。 -
コンピュータ科学 深掘り
公開鍵暗号とTLS — 鍵は渡さずに秘密を共有する
共通鍵は速いのに、その鍵をどうやって相手に渡すのかという問題だけが残ります。公開鍵暗号は、その1点だけを解く道具です。この記事では openssl で自分の鍵ペアを作り、暗号化と復号、署名と検証を実際に打ちます。RSAで長いファイルを暗号化しようとしてエラーを出し、なぜハイブリッドになるのかを確かめます。Diffie-Hellman を小さい数で計算して「鍵を送らずに同じ秘密に辿り着く」ところを見て、最後に自分だけのCAで証明書に署名し、自分で立てたHTTPSサーバーに s_client で繋いで暗号スイートを読みます。守る側だけを書きます。 -
コンピュータ科学 深掘り
トランザクションとACID — ROLLBACKしたのに戻らない
トランザクションの中で INSERT して ROLLBACK すれば戻ります。ところが途中に ALTER TABLE を1行挟むと、その前の INSERT まで確定してしまいます。暗黙のコミットです。この記事では Docker Compose で練習用の MySQL を1つ立てて、それを実際に再現します。さらに ACID を A・C・I・D と1文字ずつ壊して確かめ、BASE と PACELC で「何を捨てて速くしているのか」を対比します。正規化した3テーブルの JOIN と非正規化した1テーブルの SELECT を同じデータで測り、最後にストアドプロシージャ・クラスタリング・フェデレーションまで触ります。使うのは練習用のDBだけで、最後に docker compose down -v で全部消します。