具有更好LINQ性能的SortedSet/SortdList

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（logn）中下限和上限的二进制搜索进行排序，可以更快地完成。

第二个例子-SelectMany over集合列表：

        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 toSQL对象利用排序，它可以有效地将所有排序集拉链合并到O（n）中的一个大排序列表中。由于列表已经排序，因此可以忽略结果上的.OrderBy。

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

我的问题是：是否已经有一种更高效的LINQ to SortedSet/SortdList的替代实现

i4o看起来非常有趣，但它似乎需要辅助索引集合来提高原始集合的查询性能。我只是想利用排序的优势，让对已排序集合的查询运行得更快。

Answer 1

LINQ的问题是它不知道排序集的排序方式与查询期望的完全相同。由于任何有序集合都可以用IComparer/IComparable/Comparison<T>创建，因此不知道> 500000实际上是有意义的。也许你在比较器上有一个自定义方法，它先按奇数/偶数排序，然后按数字排序。在这种情况下，顺序将完全混乱，并且在所有情况下都需要O（n）。

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

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

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

Linq到SQL和实体框架使用IQueryable，并将实际将您的Linq查询转换为SQL，并让服务器处理索引、排序、过滤等。