ブログ · 12 ページ目
開発とデザイン、あとは雑記。
一貫性ハッシュ：マシンを 1 台足してもほぼ全鍵を並べ直さない理由
剰余による分割は台数が変わるとほぼ全データが移動します。ハッシュ空間を環にして時計回りで最初のノードに割り当てれば、動くのは 1 区間だけ。代償は仮想ノードです。
五目並べの勝敗判定：置いた 1 点だけ見れば足りる
着手ごとに盤面全体を走査するのは無駄です。勝敗は最新の 1 手でしか変わりません。置いた点から 4 方向へ伸ばして数えれば、盤面の大きさに依りません。
スライディングウィンドウ：「窓が何を保つか」を先に決める
窓が成立するのは、窓の妥当性が左右の端に対して単調に変わる場合です。保つ状態と縮める条件を先に書き出せば、2 ポインタの二重構造は自然に O(n) に償却されます。
単調スタック：「次に大きい要素」を O(n²) から O(n) へ
各添字は高々 1 回 push され 1 回 pop されるので、二重ループに見える形が線形になります。左右で最初に大きい／小さいものを探す形なら、同じ雛形が使えます。
2 進数に 1 がいくつあるか：ループから SWAR まで
popcount には 3 通りあります。1 の個数だけ回すループ、表引き、そしてビット列を並列に数える SWAR。桁違いに差が出ますが、Rust と WebAssembly は既に単一命令として持っています。
Union-find：2 行の最適化で 1 回の操作がほぼ定数になる
経路圧縮は木を平らにし、サイズによる併合は木を高くしません。両方入れて初めて計算量が逆アッカーマン関数に落ち、実用上は 5 を超えません。