用于快速筛选的 .NET 集合(排序集合)

本文关键字：集合 排序 NET 筛选 用于 | 更新日期: 2023-09-27 18:34:08

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

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

  1. 从文件中读取排序的集合并使用 Protobuf-net (v2( 反序列化
  2. 从排序集合中，基于开始和结束整数(名称 .RangeFromTo() (进行筛选
  3. 从同一排序集合中，获取集合的下一个元素(名称 .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%。如果我改用列表，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 的 Find 操作(通常(需要 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]++].

代码可以在这里找到。

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

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

用于快速筛选的 .NET 集合(排序集合)

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

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