在分析一个非常慢的方法时，我发现滞后在于搜索和过滤集合。
该方法执行以下操作(按顺序)。根据分析器，80% 的时间花在步骤 1-3 上。
- 从文件中读取排序的集合并使用 Protobuf-net (v2) 反序列化
- 从已排序的集合中，根据开始和结束整数进行过滤(名称
.RangeFromTo()) - 从同一个排序集合中，获取集合的下一个元素(name .
Right()) - 执行一些任务...
.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 .
很难相信这种类型的列表还没有在互联网上的某个地方实现。如果可能的话，我想使用一个图书馆，这样我就不必管理自己的列表。
互联网上是否存在这样的实现？
最佳答案
如果您的数组足够小(可能少于 10-20 个元素)，那么简单的线性搜索很有可能就足够了(List 在某种程度上表明您的测量速度更快)并且您可以使用 Where/TakeWhile 剪切范围:
(new[]{3,7,9,12}).Where(i => i>= 2).TakeWhile(i => i <= 9)
关于c# - 用于快速过滤的 .net 集合(排序集合)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19188345/