C# 中的老化数据结构

Question

我想要一个允许查询的数据结构 最后有多少项目 X 分钟. 。一个项目可能只是一个简单的标识符或更复杂的数据结构，最好项目的时间戳将在项目中，而不是存储在外部（作为散列或类似的，不希望出现多个具有相同项目的问题）时间戳）。

到目前为止，似乎使用 LINQ，我可以轻松过滤时间戳大于给定时间的项目并聚合计数。尽管我还犹豫是否要尝试将 .NET 3.5 特定的东西应用到我的生产环境中。对于类似的数据结构还有其他建议吗？

我感兴趣的另一部分是 老化 旧数据输出，如果我只想询问不到 6 小时前的项目计数，我希望从我的数据结构中删除任何早于该数据的项目，因为这可能是一个长时间运行的程序。

Answer 1

为此可以使用一个简单的链表。

基本上，您在末尾添加新项目，并从一开始就删除太旧的项目，这是一种廉价的数据结构。

示例代码：

list.push_end(new_data)
while list.head.age >= age_limit:
    list.pop_head()

如果清单足够繁忙，需要一次切掉比一个更大的部分，那么我同意 dmo, ，使用树结构或类似的结构，允许在更高级别进行修剪。

Answer 2

我认为一个重要的考虑因素是查询频率与查询频率。添加/删除。如果您要进行频繁的查询（特别是如果您有一个很大的集合），B 树可能是最佳选择：

http://en.wikipedia.org/wiki/B-tree

您可以让一些线程定期检查并清理这棵树，或者将其作为搜索的一部分（同样，取决于使用情况）。基本上，您将进行树搜索以找到“x 分钟前”的位置，然后计算时间较新的节点上的子节点数量。如果您保持节点下子节点的数量是最新的，那么这个总和可以很快完成。

Answer 3

具有滑动过期功能的缓存将完成这项工作......

将您的物品放入其中，缓存会处理老化......

http://www.sharedcache.com/cms/