2

サイズが無限に大きくならない時間ベースの辞書ハッシュテーブルを作成する必要があります。

「時間ベース」とは、時間 X に辞書を追加する場合、アイテムが X+Y 時間に存在しないようにすることを具体的に意味します。Y はタイムアウト期間です。

時間を辞書に保存するか、キーまたは値の構造体として保存します。

環境：

使用しているライブラリによって呼び出される「コールバック」を取得すると、4 つの情報 (時間、キー、値、操作タイプ) が得られます。

operationType は start または end にすることができます (他にもありますが、問題ではありません)。

したがって、X 後の Y 期間内に終了する場合は、この有用な情報を喜んで使用します。そうでなければ、私はそれを捨てることができます。

質問：

これは基本的に、Y間隔ごとに辞書をクリーンアップするタイマースレッドであり、メインスレッドはコールバックからこの辞書に何かを追加し続けますか?

Dictionary を使用してタイマーを使用せずにこれを行うと、「結合」できる要素を削除しても、無限に成長するように見えました。

また、このようなことを行うある種の .NET ライブラリはありますか?

4

1 に答える 1

1

プライオリティ キュー (または最小ヒープのみ) と関連するディクショナリを使用すると、コレクション全体を定期的にスキャンする必要がなくなります。残念ながら、.NET Framework にはプライオリティ キュー コレクションは含まれていませんが、利用可能なものはいくつかあります。しばらく前に単純なバイナリ ヒープを公開しました。

ここでの考え方は、アイテムを追加するときに、それをディクショナリとヒープに追加するというものです。キーでアイテムを検索する場合は、辞書で検索します。ヒープから最初の項目を削除する場合は、ヒープから取得し、キー (データの一部) を使用してディクショナリから削除します。

すばらしい点は、ディクショナリ全体をスキャンして削除する必要があるものを判断するのではなく、ヒープの一番上を確認できることです。

while (heap.Count > 0 && heap.Peek().ExpirationTime < time)
{
    var item = heap.RemoveRoot();
    dictionary.Remove(item.Key);
}

このアプローチの主な欠点は、ディクショナリ エントリのオーバーヘッドがあるため、少し多くのメモリが必要になることです。

于 2013-01-23T01:32:35.830 に答える