C#中的CircularBuffer IDictionary？

Question

我需要一个CircularBuffer IDictionary.任何人都可以指出我一个良好的开源实现.

所以IDictionary具有最大容量,比如说配置为100个项目,当添加项目101时,从字典中弹出/删除原始的第一个项目,从而确保项目计数永远不会超过100.

谢谢

Answer 1

要保持O(1)插入(删除最旧的项目超过100)和O(1)查找,您将需要一个实现IDictionary的类并保留内部有序列表.如果内存更受关注,那么BST实现SortedList可能更合适.无论如何,你的班级将包含a T[]和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)出列.

Answer 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