3

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

该方法执行以下操作（按顺序）。根据 profiler 的说法，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

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

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

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

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

https://github.com/cchanpromys/so_19188345

它将SortedArrayC5 与SortedSet.Net 进行比较。到目前为止，结果如下：

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]++]。

代码可以在这里找到。

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

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

4

1 回答 1

0

如果您的数组足够小（可能在 10-20 个元素以下），那么简单的线性搜索很有可能就足够好（这List在您的测量中更快显示出来）并且您可以使用Where/剪切范围TakeWhile：

  (new[]{3,7,9,12}).Where(i => i>= 2).TakeWhile(i => i <= 9)
于 2013-10-04T18:43:42.090 回答