c# - C#のCircularBuffer IDictionary?

Question

CircularBuffer IDictionary が必要です。誰かが私に良いオープンソースの実装を教えてくれますか?

したがって、最大容量を持つ IDictionary は、たとえば 100 項目に構成され、項目 101 が追加されると、元の最初の項目がディクショナリからポップ/削除されるため、項目数が 100 を超えないようにします。

ありがとう

score 12 · Accepted Answer

O(1) 挿入 (100 を超える最も古いアイテムの削除) と O(1) ルックアップを維持するには、IDictionary を実装し、内部の順序付きリストを保持するクラスが必要です。メモリがより重要な場合は、次のような BST 実装SortedListがより適切になる可能性があります。とにかく、クラスには aT[]と a Dictionary<T,K>(またはSortedList<T,K>) の両方が含まれます。独自の循環バッファーインデックス作成 (簡単) を行い、追加、削除などのメソッドで両方のコレクションを最新の状態に保ちます。あなたが持っているでしょう：

O(1) エンキュー (後ろへ)
追加の順序に違反する O(n) 挿入 (配列を最新の状態に保つ必要があるため)。とにかくこれは必要ないでしょう
O(1) デキュー (フロントから)
O(1) または O(log n) キー付きルックアップ

ジェネリックにして実装するIDictionary<T,K>とIDictionary、そうしない理由がなく、パフォーマンスが向上します。

重要な考慮事項の 1 つ: 重複したキーについてはどうしていますか? 実際には重複を保持できないと想定しているので、次のようにします。

例外をスローします (重複するキーがない場合は、何かを 2 回挿入すると単純にエラーになります)。
Count後ろに移動:辞書のを確認してから、this[key]インデクサーを使用してキーを挿入します。サイズが大きくなった場合は、リストがすでに最大容量に達しているかどうかを確認し、リストと辞書から前の項目を削除して、新しい項目を後ろに追加します。ディクショナリのサイズが増えていない場合は、アイテムをリスト内の既存の場所からリストの後ろに移動します。
移動せずに上書き: 前の項目と同じですが、リストをいじる必要はありません。

最後に、内部リストは値ではなくキーを保持することに注意してください。これは、リストの容量を超えたときに O(1) デキューを確実にするためです。

score 5 · Accepted Answer

5分間のグーグル検索で2つ見つかりました：

無料で使用でき、完全に実装された循環バッファーのように見えます: http://www.codeproject.com/KB/recipes/circularbuffer.aspx
フリーであることの証明: http://www.codeproject.com/KB/recipes/circularbuffer.aspx ?msg=402807#xx402807xx
明確なライセンスなし、おそらく通常の著作権、スレッドセーフ、非境界循環バッファ: http://blog.umut.tezduyar.com/2008/06/c-circular-buffer-not-thread-safe.html

score 3 · Accepted Answer

私はそのような実装を知りませんが、自分で実装するのは難しくないようです。辞書には固有の順序がないため、辞書のキーまたは値の型には、辞書に挿入された順序を表すプロパティが必要です。次に、Addメソッドのオーバーライドで、カウントが最大かどうかを確認できます。その場合は、既存のキーと値のペアを調べて、挿入順序プロパティが最も低いものを見つけ、それを新しいキーと値のペアに置き換えます。それ以外の場合は、通常どおり新しいキーと値のペアを挿入します。

score 2 · Accepted Answer

少し前に C# 3.0 で循環バッファーの完全な実装を作成し、 CodePlexでソースをリリースしました。これは BCL 設計ガイドラインに従っており、からの適切なインターフェイスをすべて実装していますSystem.Collections。

Dictionary<TKey, TValue>の代わりにをバッキングコレクションとして使用するように適応させるのは非常に簡単だと思いますList<T>。

score 0 · Accepted Answer

System.Data.Sqlite ( http://sqlite.phxsoftware.com/ ) ラッパーを介して SQLite データベーステーブルを使用することで、これに似たものを実装しました。ディスクに保存することも、メモリ内データベースとして保存することもできます。一意のキーを持つかどうかを選択して、データベースエンジンにインデックス作成を処理させることができます。キーごとに複数の値を持つこともできます。

テーブルに書き込むときは、100 レコードの制限に達しているかどうかを確認し、制限されている場合は、挿入する前に削除してください。一意のキーを保持したい場合、SQLite は「挿入または置換」コマンドをサポートします。おそらく、これはカスタムの IDictionary 派生ほどエレガントではありませんが、機能し、柔軟性があり、スレッド間で容易に共有できます。

score 0 · Accepted Answer

これはどう：

    public class CircularDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    {
        private Queue<TKey> m_ItemInsertList = new Queue<TKey>();
        private int m_ItemsToHold = 100;

        public int ItemsToHold
        {
            get { return m_ItemsToHold; }
            set {
                if (value < 1)
                    throw new ArgumentException("Items to hold must be at least 1");
                m_ItemsToHold = value; 
            }
        }

        public new void Add(TKey key, TValue value)
        {
            base.Add(key, value);
            if (m_ItemInsertList.Count == m_ItemsToHold)
                base.Remove(m_ItemInsertList.Dequeue());
            m_ItemInsertList.Enqueue(key);
        }
    }

c# - C#のCircularBuffer IDictionary?

6 に答える 6

Related

Reference