1. 問題
StableBoundedPriorityQueue を実装します。各エントリは priority、sequence、および value を持ちます。最初に priority を比較し、次に sequence を比較します。容量 C において、push は最大 C 個のエントリを保持します。新しいエントリは、現在の最悪のエントリより優れている場合にのみそのエントリを置き換えます。それ以外の場合は拒否されます。pop は最良のエントリを返します。
2. 制約と確認事項
Cは正の整数です。C=0の場合、配列の境界に触れることなくすべての挿入が拒否されます。- 数値が小さいほど優先度が高くなります。同一優先度のものは挿入順に取り出される必要があります。
- キューが満杯のときに最悪の要素を拒否するには、その要素を見つける必要があります。単一の最小ヒープではそれを
O(log C)で直接公開できないため、第2のインデックス、最大ヒープを使用するか、線形探索を受け入れる必要があります。 - まずはシングルスレッド実装から始めてください。並行プロデューサーおよびコンシューマーには、外部ロックまたは専用の並行キューが必要です。
3. コアアプローチ
次の要素用には、(priority, sequence) で順序付けられた最小ヒープを使用します。最悪の要素用には、優先度が大きくシーケンスが遅いほど悪いとみなす順序付けの最大ヒープを使用します。両方のヒープは同じエントリレコードを指します。削除時はエントリに alive=false のマークを付けます。各ヒープは無効なノードがルートに到達したときにそれを破棄します。この遅延削除により、ヒープの任意位置の削除を回避できます。
小規模な容量の場合、最悪の要素に対する線形探索の方がシンプルです。pop は O(log C) のままであり、満杯キューへの push には O(C) がかかります。2ヒープ最適化を提示する前に、このトレードオフを説明してください。
4. 参照実装
record Entry(priority, sequence, value, alive=true)
push(priority, value):
if capacity == 0: return false
candidate = Entry(priority, nextSequence(), value)
if size < capacity:
add candidate to minHeap and maxHeap
size += 1
return true
discard dead nodes from maxHeap
worst = maxHeap.peek()
if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
return false
worst.alive = false
pop maxHeap
add candidate to both heaps
return true
pop():
discard dead nodes from minHeap
if minHeap is empty: return EMPTY
entry = pop minHeap
entry.alive = false
size -= 1
return entry.value最大ヒープのキーは「大きいほど悪い」ことを意味します。優先度が大きいほど悪く、同一優先度の場合はシーケンスが大きいほど後から来たため悪くなります。言語に最大ヒープがない場合は、キーを反転するか比較関数を提供してください。nextSequence は単調増加である必要があります。幅の広い整数を使用するか、キューが空のときにのみリセットしてください。
5. 計算量とトレードオフ
受け入れられた挿入は各ヒープに1つのノードを追加するため、O(log C) のコストがかかります。pop のコストは O(log C) です。置き換えも O(log C) です。遅延削除により一時的に無効ノードが残る場合がありますが、各無効ノードがポップされるのは1回だけであるため、ならし計算量は O(log C) 操作となり、空間計算量は定数倍の増加を伴う O(C) となります。線形探索のバリエーションは空間が少なくコードも短くなりますが、満杯キューへの挿入に O(C) のコストがかかります。
6. 検証と可観測性
C=0、C=1、空のキュー、繰り返される拒否、および繰り返される置き換えを網羅します。- 同一優先度のエントリを複数挿入し、シーケンスによるFIFO順序を検証します。
- 満杯のキューに対してより悪い候補、同一の候補、より良い候補をテストし、拒否、拒否、置き換えとなることを確認します。
- ランダムな操作トレースを、すべての有効なエントリを
(priority, sequence)でソートしてCに切り詰める参照モデルと比較します。 - キューの長さ、拒否数、および遅延ノードのクリーンアップ数を記録します。拒否率の上昇は、アップストリームのスロットリングや負荷遮断をトリガーできます。
7. よくある間違い
- 優先度のみでソートしてしまい、同順位におけるFIFOの安定性が失われる。
- 順序の方向を確認せずに、数値が大きい優先度の方が重要であると思い込む。
- 受付前にヒープのルートをポップしてしまい、キューが満杯のときに最良のタスクを破棄してしまう。
- 無効ノードの破棄に失敗し、
peekがすでに置き換えられたかキャンセルされたエントリを返してしまう。 - シーケンス番号に実時間タイムスタンプを使用する。クロックの巻き戻りや同一ティック内での挿入によってFIFOが壊れる可能性があります。
8. 発展的な質問
テナントごとのクォータをどのように適用しますか？
各テナントのカウントと制限を保持します。挿入前にグローバル容量とテナントクォータの両方をチェックし、高負荷のテナントを可視化できるように2つの拒否理由を個別にカウントします。
エントリのキャンセルや優先度変更はどのように行いますか？
各エントリにIDを付与し、遅延削除を使用します。キャンセル時は無効のマークを付けます。優先度変更時は新しいエントリを作成し、古いエントリを無効化します。任意のヒープ位置を削除する代わりに、ピークまたはポップの際に無効ノードをクリーンアップします。
ライブラリの並行優先度付きキューを使用すべきなのはどのような場合ですか？
複数のスレッドまたはプロセスが生成・消費する場合、ブロッキング待機が必要な場合、またはメモリ制限が厳しい場合は、検証済みの並行実装を使用します。カスタムの2ヒープ設計は、明確なシングルスレッドの境界とテスト可能なライフサイクルがある場合にのみ適切です。