-
コンピュータ科学 深掘り
グラフと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 で全部消します。 -
コンピュータ科学 深掘り
デザインパターンとDI — テストが書けないのは設計のせい
注文処理の中で new Mailer() をしていたら、テストを走らせただけで ECONNREFUSED が出ました。テストが書けないのは自分の腕ではなく、設計のせいでした。この記事では「中で作る」のをやめて「外から受け取る」に変えるだけで node --test が通るところを、実際に走らせて確かめます。そのうえで個人開発で本当に出てくる5つのパターンだけを Before / After のコードで比べ、Null Object と Type Object で if とクラス爆発を消します。最後に「2つの数を足す」だけの処理にパターンを4つ重ねた実物を作り、素朴な1行版と行数とファイル数で比べます。 -
コンピュータ科学 深掘り
SSEとWebSocket — 1秒ごとに聞きに行くのをやめる
1秒ごとに「新着ありますか」と聞きに行くコードを書いて、60秒で59回投げて53回が空振りだったところまで実測します。その手前で、Node.js の net で素のTCPサーバーを書き、200回 write したのに data イベントが17回しか起きないところを再現します。TCP にはメッセージの区切りが無いからです。改行区切りと長さプレフィックスの両方で直します。UDP と比べ、ロングポーリングで59回を7回に減らし、最後に SSE の生バイト列と WebSocket の 101 応答を curl で取り、フレームを1つ手で解読します。