深掘り– tag –
-
システム設計 深掘り
メッセージキューの型 — 急ぎの仕事が後ろで待つ
キューを1本立てたら、5分かかる動画変換の後ろで、1秒で終わるパスワード再設定メールが待たされました。キューは「1本立てれば終わり」ではなく、型があります。この記事では RabbitMQ を1つ立て、同じメッセージを「分担する」形と「全員に配る」形の両方を実際に作り、ワーカーを2つ並べて届き方の違いを目で見ます。続いてワーカーを増やして処理時間が縮むのを実測し、prefetch を設定しないと遅いワーカーに仕事が積まれることを再現して直します。優先度キューでは急ぎを先に通したうえで、優先度の低い仕事が永久に処理されない飢餓をわざと起こし、対策を3つ比べます。さらに300件を一気に投げて負荷平準化を実測し、リトライの回数制限とデッドレターキューを実際に作り、順序が要る場合の2つの逃げ道、遅延キューやファンアウトの型、そして「キューを使わない」という選択まで。最後に立てたものを全部消します。 -
コンピュータ科学 深掘り
スタックとキュー — call stack size exceeded の正体
終わらない再帰を書いて Maximum call stack size exceeded を出したとき、私は「JavaScriptが疲れた」くらいの理解でした。実際は、自分がその日 push と pop で作ったのと同じものが、言語の内側で溢れていただけでした。この記事では VM の中に ~/cslab/sq を作り、スタックとキューを手で書きます。全部 O(1) であることを実測し、わざとエラーを出して積める段数を数え、スタックトレースが下から読める理由を出力で確かめます。キューは配列の shift() で作ってから 10万件で測り、先頭の位置を持つ形に直して同じ測定で速くなることを見ます。最後に setTimeout と Promise の実行順を出して、イベントループもキューだったことを確かめて全部消します。 -
コンピュータ科学 深掘り
バランス木とB木 — 100万件が3段で届く
二分探索木は「毎回半分に絞れるから速い」と習いました。ところが 1,2,3,... と並んだ 10,000件を入れたら、高さが 10,000 になりました。木ではなく連結リストです。この記事では VM の中に ~/cslab/btree を作り、その症状を実測してから AVL木を自分で書きます。回転を図で暗記せず、単回転と二重回転を実装して、同じ 10,000件で高さが 14 に収まることを確かめます。赤黒木は実装せずルールだけ読み、B木がなぜデータベースの索引なのかを段数の計算で出します。最後にトライでオートコンプリートを作り、スキップリストと比べて、全部消します。 -
コンピュータ科学 深掘り
ハッシュテーブル — 10万件のincludesで止まる
10万件の配列に includes を書いたら画面が止まりました。Set の has に変えたら一瞬で終わり、そのとき私は「Setは速い」で納得してしまいました。この記事では VM の中に ~/cslab/hash を作り、その差が何倍あるのかを実測してから、ハッシュ関数とハッシュテーブルを自分の手で書きます。バケットの中身を表示して、どのキーがどこに入ったかを目で見て、わざと衝突させて O(1) が O(n) に落ちる瞬間を表にします。負荷率とリサイズを実装して、リサイズが起きた15回だけ平均の3万倍遅くなることを測ります。最後にハッシュと暗号化とエンコードを sha256sum と base64 で並べて確かめ、Object と Map と Set と WeakMap の使い分けを表にして全部消します。 -
コンピュータ科学 深掘り
ヒープとLRUキャッシュ — 10件欲しいだけで100万件ソート
ランキングの上位10件を出すために、私は100万件を毎回まるごとソートしていました。必要なのは10件なのに、残りの999990件を丁寧に並べ替えていたわけです。この記事では VM の中に ~/cslab/heap を作り、サイズ10のヒープを手で書いて、全部ソートする版と実測で比べます。ヒープが「木なのにポインタを1つも使わず、配列1本で持てる」ことを添字の計算で確かめ、内部配列を表示してヒープがソートされていないことを見ます。後半はLRUキャッシュを素朴な O(n) 版から O(1) 版へ直し、容量を変えながらヒット率を実測します。最後に LRU・LFU・MFU・FIFO・ランダムを同じアクセス列で走らせ、LFU が「昔たくさん使われたもの」に居座られて負ける瞬間を数字で出してから、全部消します。 -
コンピュータ科学 深掘り
線形探索と二分探索 — 1回引くだけなら並べると損
「二分探索のほうが速い」は、並べる時間を勘定に入れていない。ソートは O(n log n)、探索は O(log n)。1回しか引かないなら、線形探索のほうが速い。何回引いたら並べるべきかを、実際に交差点が出るまで測る。二分探索の実装でよく踏む3つの間違いをわざと出して直し、「見つからないときどこに入れるか」を返す版まで作る。最後にハッシュとの使い分け、総当たりが正解になる場面、そして git bisect が二分探索そのものだという話。 -
コンピュータ科学 深掘り
ソートアルゴリズム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・問題を小さくする・時間で打ち切る)を実装して、最適解・所要時間・実装の手間を表にします。