ブログ · 8 ページ目
開発とデザイン、あとは雑記。
スライディングウィンドウ：「窓が何を保つか」を先に決める
窓が成立するのは、窓の妥当性が左右の端に対して単調に変わる場合です。保つ状態と縮める条件を先に書き出せば、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 を超えません。
Rust の Result：コンテキストは失敗した行に付ける
`?` はエラーをそのまま上へ投げ、どの段階で失敗したかを伝えません。中核は照合できる構造化エラー、アプリ層は Context で「何をしていたか」と入力を添える。
crate を workspace に分けるべきとき
分割の引き金はビルド時間と依存の境界で、ディレクトリの見た目ではありません。3 つの条件が揃ったときに分け、揃わなければ 1 回のビルドを複数パッケージの管理と引き換えにするだけです。