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

Question

假设我们有一个排序集合,例如SortedSet或SortedList,有很多(10M +)元素.大量的查询正在发生,因此性能很重要.从运行时比较,我的印象是,LINQ到对象不采取排序的优势,因此不能服用的潜在性能提升的优势下.

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

        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)的下限和上限,可以更快地完成.

第二个示例 - 在集合列表上选择多个:

        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实际上是否有意义.也许你在比较器上有一个自定义方法,首先按Odd/Even排序,然后按数字排序.在这种情况下,订单将完全搞砸,并且在所有情况下都需要O(n).

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

有可能创建一个优化版本,在迭代时记住现有的排序,但是要做到并且在所有情况下都能使用它将非常困难.

您可以创建一个Between方法,使用该GetViewBetween方法SortedSet返回新的预先订购的集合.或者.Where按照通常对任何非预先排序的集合添加标准.

如果IQueryable将Linq-to-SQL和Entity Framework用于实际将Linq查询转换为SQL并让服务器处理索引,排序,过滤等.