c# - 用于快速过滤的 .net 集合(排序集合)

Question

在分析一个非常慢的方法时，我发现滞后在于搜索和过滤集合。

该方法执行以下操作(按顺序)。根据分析器，80% 的时间花在步骤 1-3 上。

1. 从文件中读取排序的集合并使用 Protobuf-net (v2) 反序列化
2. 从已排序的集合中，根据开始和结束整数进行过滤(名称 .RangeFromTo())
3. 从同一个排序集合中，获取集合的下一个元素(name .Right())
4. 执行一些任务...

.RangeFromTo() 过滤给定范围，例如:

[3,7,9,12].RangeFromTo(2,9) -> [3,7,9]
[3,7,9,12].RangeFromTo(2,8) -> [3,7]
[3,7,9,12].RangeFromTo(7,13) -> [7,9,12]
[3,7,9,12].RangeFromTo(13,14) -> [ ]

.Right() 在集合中找到一个元素并为您提供列表中的下一个元素。如果该元素不存在，它会为您提供最接近右侧的元素。例如:

[3,7,9,12].Right(0) -> 3
[3,7,9,12].Right(3) -> 7
[3,7,9,12].Right(4) -> 7
[3,7,9,12].Right(12) -> null

目前该集合使用来自 C5 (https://github.com/sestoft/C5/) 的 SortedArray。有没有更适合我使用的集合？

注意:步骤 1. 大约占总时间的 30%。如果我改用 List，protobuf 反序列化的时间实际上减少了 40%!我想当插入到 SortedArray 中时，集合不知道数据已经排序并且正在做一大堆工作。理想的集合(如果存在的话)也应该能够绕过它。

编辑:澄清一下，列表大约有 1000-5000 个，并且有 90k 个不同的集合!有问题的方法需要加载内存中的所有集合以执行某些业务任务。

编辑 2:我在这里添加了一些示例基准:

https://github.com/cchanpromys/so_19188345

它将 C5 的 SortedArray 与 .Net 的 SortedSet 进行比较。至此结果如下:

C5 sorted array deserialize took 904
Sorted set deserialize took 1040
C5 sorted array .Right() took 5
Sorted set .Right() took 798    <--- Not sure what happened here...
C5 sorted array .RangeFromTo() took 217
Sorted set .RangeFromTo() took 140

编辑 3这超出了我的预期，但我最终得到了一个列表的自定义实现。

我遇到的问题是 SortedArray 的查找操作(通常)需要 O(Log(N))，而我希望它是 O(1) 操作。

另外，列表是自然排序的，你永远不会添加到列表的中间。

所以我最终实现了一个具有内部索引器数组的列表，例如:

例如:

indexer: [0,0,0,0,1,1,1,1,2,2]
list: [3,7,9]

所以 .Right(3) 将是 list[indexer[3]++]。

可以查到代码here .

很难相信这种类型的列表还没有在互联网上的某个地方实现。如果可能的话，我想使用一个图书馆，这样我就不必管理自己的列表。

互联网上是否存在这样的实现？

Answer 1

如果您的数组足够小(可能少于 10-20 个元素)，那么简单的线性搜索很有可能就足够了(List 在某种程度上表明您的测量速度更快)并且您可以使用 Where/TakeWhile 剪切范围:

  (new[]{3,7,9,12}).Where(i => i>= 2).TakeWhile(i => i <= 9)