C#中的CircularBuffer IDictionary？

发布时间：2020-12-15 19:54:40 所属栏目：百科来源：网络整理

导读：我需要一个CircularBuffer IDictionary.任何人都可以指出我一个良好的开源实现. 所以IDictionary具有最大容量,比如说配置为100个项目,当添加项目101时,从字典中弹出/删除原始的第一个项目,从而确保项目计数永远不会超过100. 谢谢解决方法要保持O(1)插入(删

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

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

谢谢

解决方法

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

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

使其成为通用的并实现IDictionary< T,K>和IDictionary,因为没有理由不这样做,你将获得性能优势.

一个主要考虑因素：你如何处理重复键？我假设你实际上不能保留重复,所以：

>抛出一个异常(如果没有重复的密钥,那么插入两次只是一个错误)
>向后移动：检查字典的计数,然后使用此[key]索引器插入密钥.如果大小增加,则检查列表是否已具有最大容量,从列表和字典中删除前项并将新项添加到后面.如果字典的大小没有增加,请将项目从列表中的现有位置移动到列表的后面.
>不移动覆盖：与上一个项目相同,但您不必弄乱列表.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!