相关疑难解决方法(0)

假设我们有一个排序集合,例如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看起来很有趣,但它似乎需要二级索引集合来提高原始集合的查询性能.我只是希望通过利用排序来对我的已排序集合进行查询以更快地运行.