テーマ： algorithms

• グラフ探索で依存順序を求める：BFS、DFS、トポロジカルソート

  依存関係を有向グラフとして表し、幅優先または深さ優先探索で変更の影響範囲を求めます。Kahn のアルゴリズムや DFS の帰りがけ順で、循環を隠さず報告するビルド・移行順序を作ります。graphlib と tsort がこのソートを実装しています。

  methodology · ja · reviewed · 知識の基準日 2026-09-16

• 実用的なハッシュテーブル：衝突、負荷率、シード付きハッシュ

  ハッシュテーブルが平均して速いのは、キーがバケットへ均等に分散するときだけです。衝突、再ハッシュを起こす負荷率、ハッシュ洪水攻撃を防ぐプロセスごとのシードが、実際の動作を決めます。ハッシュ値を永続化せず、反復順序にも依存しないようにします。

  article · ja · reviewed · 知識の基準日 2026-09-16

• 動的計画法を順に学ぶ：編集距離の導出

  動的計画法は、重複する部分問題を持つ再帰的な定義を多項式時間のアルゴリズムに変えます。状態、漸化式、基底ケースを定め、メモ化または表の計算を行い、最後にメモリを削減します。二つの文字列の編集距離を例に、導出全体を示します。

  methodology · ja · reviewed · 知識の基準日 2026-09-16

• Recursion versus iteration: stack depth, limits and when to convert

  Recursion mirrors tree-shaped problems but spends one stack frame per level; the stack is bounded by the interpreter's recursion limit or the thread's stack size, so recursion over input-controlled depth is a crash waiting to happen. Convert to an explicit stack or loop when depth grows with input size.

  article · en · reviewed · 知識の基準日 2026-09-16

• リザーバサンプリング：長さが不明なストリームから一様に抽出する

  長さを知らずにストリームから k 個を保持します。最初の k 個でリザーバを埋め、その後の項目 i では確率 k/i でランダムなスロットを置き換えます。一回の走査、O(k) のメモリで、各項目が最終標本に入る確率は正確に k/n です。短い積の相殺による議論で示せます。

  methodology · ja · reviewed · 知識の基準日 2026-09-16

• トライによる接頭辞検索：自動補完と最長接頭辞一致

  トライは共通の接頭辞ごとにノードを持って文字列を保存するため、検索コストはキー数ではなくキー長で決まります。同じ接頭辞のキーは一つの部分木になり、保存済みの最長接頭辞は一回の探索で見つかります。自動補完やルーティングに使えますが、先にソート済み配列と比較します。

  article · ja · reviewed · 知識の基準日 2026-09-16

• 二分探索の落とし穴：中点のオーバーフローと境界のオフバイワンエラー

  二分探索は短いものの、間違えやすいことで知られます。(low + high) / 2 は固定幅整数をオーバーフローさせ、包含・除外境界は混同しやすく、重複値があると返すインデックスも問題になります。ライブラリ、または半開区間と単調な述語を使い、端のケースをテストします。

  article · ja · reviewed · 知識の基準日 2026-09-16

• Reasoning about complexity before optimising

  Asymptotic complexity predicts how run time grows with input size; recognising quadratic loops, repeated linear searches and unbounded recursion in code review prevents most performance incidents before profiling is needed.

  methodology · en · reviewed · 知識の基準日 2026-09-15

• Token bucket, leaky bucket and sliding window: how rate-limiter algorithms differ

  Fixed windows are cheap but let twice the limit through at a boundary; sliding logs are exact but store every timestamp; sliding-window counters approximate in constant memory; token buckets allow bursts up to the bucket size at a fixed refill rate; leaky buckets smooth output by delaying. nginx and Envoy document the last two.

  article · en · reviewed · 知識の基準日 2026-09-16

• Bloom フィルター：偽陰性のない確率的な集合所属判定

  Bloom フィルターは小さなビット配列と k 個のハッシュ関数で、「確実に集合にない」または「おそらく集合にある」と答えます。偽陽性率は調整でき、偽陰性はなく、削除はできません。存在しないキーの検索を省くために使い、陽性の結果は必ず正本のデータと照合します。

  article · ja · reviewed · 知識の基準日 2026-09-16

• A* heuristics: preserve the meaning of movement cost

  Choose a lower-bound heuristic for the actual movement graph, handle improved routes correctly, and verify path quality against an uninformed search.

  article · en · unreviewed · 知識の基準日 2026-10-11

• Use a token bucket for tool calls

  Implement bounded bursts with an explicit token refill equation, atomic consumption and a separate limit on in-flight requests.

  methodology · en · reviewed · 知識の基準日 2026-09-21

• ソートの安定性：何を保証し、いつ重要になるか

  安定ソートは、比較結果が等しい要素の入力時の順序を保つ。Python はこれを保証し、ECMAScript は2019年以降必須としている。Go と GNU sort では選択でき、複数キーのソート、並べ替え可能な表、ページ分割クエリの予測可能性を左右する。

  article · ja · reviewed · 知識の基準日 2026-09-16

機械可読： JSON