我有一个很大的数据集
,其中可能有超过一百万个条目。所有项目都有分配的时间戳,并且项目在运行时添加到集合中(通常但不总是使用更新的时间戳)。
我需要在给定的时间范围内显示此数据的子集。与总数据集相比,这个时间范围通常非常小,即在 1.000.000 多个项目中,给定时间范围内的项目不超过 1000 个。这个时间范围以恒定的速度移动,例如时间范围每秒移动一秒。
此外,用户可以随时调整时间范围(在数据集中“移动”)或设置额外的过滤器(例如按某些文本过滤)。
到目前为止,我并不担心性能,而是试图把其他事情做好,并且只使用较小的测试集。我不太确定如何有效地解决这个问题,并且会很高兴收到每一份意见。谢谢。
编辑:使用的语言是 C# 4。
更新:我现在使用的是区间树,实现可以在这里找到: https://github.com/mbuchetics/RangeTree
它还有一个异步版本,使用任务并行库 (TPL) 重建树。
最佳答案
我们在开发中遇到了类似的问题 - 必须收集数百万个按某个键排序的项目,然后根据需要从中导出一页。我发现您的问题有点相似。
为此,我们调整了 red-black tree结构,通过以下方式:
- 我们向其中添加了迭代器,因此我们可以在 o(1) 中获取“下一个”项目
- 我们添加了从“索引”中查找迭代器,并设法在 O(log n) 中完成
RB Tree具有 O(log n) 插入复杂度,所以我猜你的插入会很好地适合那里。
迭代器上的next()
是通过添加和维护所有叶节点的链表实现的——我们原来采用的RB Tree实现不包括这一点。
RB Tree也很酷,因为它允许您根据需要微调节点大小。通过试验,您将能够找出适合您问题的正确数字。
关于c# - 过滤(可能)1.000.000+ 项的子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4407117/