Node.js– tag –
-
コンピュータ科学 深掘り
二分探索木と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・問題を小さくする・時間で打ち切る)を実装して、最適解・所要時間・実装の手間を表にします。 -
コンピュータ科学 深掘り
再帰とメモ化 — メモを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 の実測圧縮率と並べます。最後に接尾辞配列で「何回引いたら作る価値があるか」の交差点を出します。 -
コンピュータ科学 深掘り
SSEとWebSocket — 1秒ごとに聞きに行くのをやめる
1秒ごとに「新着ありますか」と聞きに行くコードを書いて、60秒で59回投げて53回が空振りだったところまで実測します。その手前で、Node.js の net で素のTCPサーバーを書き、200回 write したのに data イベントが17回しか起きないところを再現します。TCP にはメッセージの区切りが無いからです。改行区切りと長さプレフィックスの両方で直します。UDP と比べ、ロングポーリングで59回を7回に減らし、最後に SSE の生バイト列と WebSocket の 101 応答を curl で取り、フレームを1つ手で解読します。 -
データベース
プロセスを止めても消えない場所 — MySQLとSQLの基本
前回のAPIは、サーバーを止めるとデータが消えた。なぜファイルに書くだけでは駄目なのかから始めて、MySQLを入れ、SQLの4つを覚え、最後にNode.jsから繋いで「再起動しても残る」ところまで持っていく。WHEREを忘れたUPDATEで全行が飛ぶ話つき。 -
データベース
ALTER TABLE を手で打たない — ORMとマイグレーション
SQLの文字列がコードじゅうに散らばってきた。ORMは何を解決して、何を解決しないのか。生成されたSQLを実際に表示させて「魔法ではない」ことを確かめ、テーブルの変更をコードとして残し、権限の壁(appuserはCREATE TABLEできない)を専用ユーザーで正面から片づけて、最後に必ず戻します。 -
キャッシュとキュー
キャッシュは消すのが一番難しい — Redisの導入
速くしたいから入れる、の前に必ず測る。20万件の集計を実際に遅くしてから Redis を入れ、TTL とキー設計を決め、「更新したのに古い値が返る」事故をわざと起こして直します。セッションを MySQL から Redis に移して何が変わるかと、既定で認証が無いという危険、そして入れないほうがいい場面まで。