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因为没有理由不这样做，您将获得性能优势。

一个主要考虑因素：您如何处理重复键？我假设您实际上不能保留重复项，因此：

抛出异常（如果从来没有重复的键，那么插入两次只是一个错误）
移到后面：检查字典，然后使用索引器Count插入键。this[key]如果大小增加，则检查列表是否已经具有最大容量，从列表和字典中删除前面的项目并将新项目添加到后面。如果字典的大小没有增加，则将项目从列表中的现有位置移动到列表的后面。
不移动覆盖：与上一项相同，但您不必将列表弄乱。

最后，请注意内部列表保留键，而不是值。这是为了确保在超出列表容量时 O(1) 出队。

score 5 · Accepted Answer

谷歌搜索五分钟后发现两个：

免费使用，看起来像一个完全实现的循环缓冲区： 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.

我相信它应该很容易适应使用 aDictionary<TKey, TValue>作为支持集合而不是 a List<T>。

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);
        }
    }

score 0 · Accepted Answer

我通过 System.Data.Sqlite ( http://sqlite.phxsoftware.com/ ) 包装器使用 SQLite 数据库表实现了类似的功能。您可以将其存储在磁盘上或作为内存数据库。您可以选择是否具有唯一键并让数据库引擎为您处理索引。每个键甚至可以有多个值。

当您写入表时，检查您是否处于 100 条记录的限制，如果是，则在插入之前删除。如果要保留唯一键，SQLite 支持“插入或替换”命令。也许这不像自定义 IDictionary 派生那样优雅，但它很有效，很灵活，并且很容易跨线程共享。

c# - C# 中的 CircularBuffer IDictionary？

6 回答 6

Related

Reference