最善のアプローチは、有効期限に基づく優先度を持つ優先 (最小) ヒープです。
ウィンドウの有効期限が切れるたびに、最小アイテムを O(1) 時間でヒープから削除し、有効期限に加えてウィンドウ サイズを O(log(N)) 時間で再挿入します。必要なスペースは O(N) です。
現在の時間を表すには、(少なくとも) 2 つのオプションがあります。
1) 太陽が燃え尽きるまでの時間を処理する広い値 (たとえば 64 ビット) を使用します。
2) モジュロ演算を使用します。これには慎重な比較演算子が必要です
モジュロ アプローチの場合、時間値は、少なくとも最大ウィンドウ サイズにタイマー有効期限の待機時間のわずかなマージンを加えた値と同じ大きさである必要があります。符号なし演算を使用します。ヒープ内の値は、エントリが挿入された時間である必要があります。各エントリーの残り時間は
window - (now - inserted)
(now - inserted)
これは、エントリがヒープ内にある時間の尺度であるため、常に正であることに注意してください。差がゼロを「ラップ」する場合、符号なしの結果は正しいでしょう。window
もポジティブです。2 つのエントリがx
ありy
、
(x.window - (now - x.inserted)) > (y.window - (now - y.inserted))
を使用して符号なし算術演算でこれを行うことができます
(x.window + (now - y.inserted)) > (y.window + (now - x.inserted))
これは、ヒープ エントリを比較するために使用する比較演算子です。