.net - 具有更好 LINQ 性能的 SortedSet/SortedList？

Question

假设我们有一个排序集合，例如 SortedSet或 SortedList具有许多(10M+)元素。正在发生大量查询，因此性能很重要。从运行时比较来看，我的印象是 LINQ to Objects 没有利用排序，因此没有利用潜在的性能提升。

第一个示例 - 计算范围内的元素:

        var mySortedSet1 = new SortedSet<int>();
        // populate ...
        int rangeCount = (from n in mySortedSet1
                          where ((n >= 1000000000) && (n <= 2000000000))
                          select n).Count();

不完全确定 LINQ to Objects 在内部做了什么，最坏的情况是检查每个 O(n) 的元素。通过利用对 O(log n) 中的下限和上限进行二分搜索的排序，可以更快地完成。

第二个例子 - SelectMany 在集合列表上:

        var myListOfSortedSets = new List<SortedSet<int>>();
        // populate...

        var q = myListOfSortedSets.SelectMany(s => s).OrderBy(s => s);
        foreach (var n in q)
        {
            Console.WriteLine(n);
        }

如果 LINQ to SQL Objects 要利用排序，它可以有效地将所有已排序的集合以 O(n) 的方式有效地压缩合并到一个大的排序列表中。结果上的 .OrderBy 可以被忽略，因为列表已经排序。

相反，SelectMany 将所有已排序的集合连接到一个大(现在未排序)列表中，这将需要另一个 O(n log n) 排序。这可以通过删除 .OrderBy 并观察元素写入控制台的顺序来轻松验证。

我的问题是: 是否已经有替代的、更有效的 LINQ to SortedSet/SortedList 实现？

i4o看起来很有趣，但似乎需要二级索引集合来提高对原始集合的查询性能。我只是希望通过利用排序来更快地运行对排序集合的查询。

Answer 1

LINQ 的问题在于它无法知道排序集的排序方式与查询预期的完全相同。由于可以使用 IComparer 创建任何有序集合。/IComparable/Comparison<T> ，不知道> 500000其实是有道理的。也许您在比较器上有一个自定义方法，它首先按奇数/偶数排序，然后按数字排序。在这种情况下，订单将完全困惑，并且在所有情况下都需要 O(n)。

所以为了安全起见，LINQ 需要遍历集合中的所有元素，即使它以某种方式排序。默认.Where实现不包含对有序集合的优化。

有可能创建一个优化版本，在迭代时记住现有的顺序，但很难做到并使其在所有情况下都能正常工作。

您可以创建一个 Between使用 GetViewBetween 的方法SortedSet的方法返回一个新的预购集合。或者会添加标准 .Where就像您通常对任何非预先排序的集合所做的那样。

Linq-to-SQL 和 Entity Framework 使用 IQueryable 并将您的 Linq 查询实际转换为 SQL 并让服务器处理索引、排序、过滤等。