2

独自の期間/ウィンドウを持つクライアントのリスト (A、B、C、D) があります。次のウィンドウの有効期限に基づいて内部的にタイマーを設定しました...（A、B、C、D）のウィンドウサイズの中から..

例えば：

Client Window Size
A      10
B      15
C      20
D      50

したがって、タイマーの有効期限は次のようになります: 10,15,20,30,40,45,50 ...

これを行う最善の方法は何ですか？実装する言語として C を選択します。クライアント期間は、静的に割り当てられた配列に格納されます (サイズはわかっています)

4

2 に答える 2

1

最善のアプローチは、有効期限に基づく優先度を持つ優先 (最小) ヒープです。

ウィンドウの有効期限が切れるたびに、最小アイテムを 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))

これは、ヒープ エントリを比較するために使用する比較演算子です。

于 2013-04-26T23:38:20.490 に答える