当前位置：文江博客话题详情

C# 中的 CircularBuffer IDictionary？

发布于 2024-08-01 17:12:23 字数 169 浏览 3 评论 0原文

我需要一个 CircularBuffer IDictionary。谁能指出我一个好的开源实现。

因此，一个具有最大容量的 IDictionary，假设配置为 100 个项目，当添加第 101 个项目时，原始第一个项目将从字典中弹出/删除，从而确保项目计数永远不会超过 100。

谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

呆 2024-08-08 17:12:23

不久前，我用 C# 3.0 编写了一个循环缓冲区的完整实现，并在 CodePlex 上发布了源代码。它遵循 BCL 设计准则，并实现 System.Collections 中的所有适当接口。

我相信使用 Dictionary 作为支持集合而不是 List 应该很容易适应。

回复收藏 0 原文

烟─花易冷 2024-08-08 17:12:23

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

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

回复收藏 0 原文

苦行僧 2024-08-08 17:12:23

这个怎么样：

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

How about this:

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

回复收藏 0 原文

凝望流年 2024-08-08 17:12:23

我不知道有任何这样的实现，但自己实现听起来并不难。由于字典没有任何固有的顺序，因此字典中的键或值类型都需要有一些属性来表示它插入字典的顺序。然后，在重写 Add 方法时，它可以检查计数是否达到最大值。如果是，则查找现有的键值对，找到插入顺序属性最低的键值对，并将其替换为新的键值对。否则，照常插入新的键值对。

回复收藏 0 原文

芯好空 2024-08-08 17:12:23

为了保持 O(1) 插入（删除超过 100 的最旧项目）和 O(1) 查找，您需要一个实现 IDictionary 的类并保留内部有序列表。如果更关心内存，那么像 SortedList 这样的 BST 实现可能更合适。无论如何，您的类将包含 T[] 和 Dictionary （或 SortedList）。执行您自己的循环缓冲区索引（简单），并在添加、删除等方法中保持两个集合最新。您将拥有：

O(1) 排队（向后）
O(n) 违反添加顺序的插入（因为您必须保持数组最新）；无论如何，你可能永远都不需要这个
O(1) 出队（从前面）
O(1) 或 O(log n) 键控查找

使其通用并实现 IDictionary 和 IDictionary 因为没有理由不这样做，并且您将获得性能优势。

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

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

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