7

假设我们有一个排序集合，例如带有许多 (10M+) 元素的SortedSet或SortedList 。正在发生大量查询，因此性能很重要。从运行时比较来看，我的印象是 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对象要利用排序，它可以在 O(n) 中有效地将所有排序集压缩合并到一个大的排序列表中。结果上的 .OrderBy 然后可以被忽略，因为列表已经排序。

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

我的问题是：是否已经有另一种更有效的 LINQ to SortedSet/SortedList 实现？

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

4

1 回答 1

6

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

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

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

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

如果 IQueryable 可以使用 Linq-to-SQL 和实体框架，并且实际上会将您的 Linq 查询转换为 SQL，并让服务器处理索引、排序、过滤等。

于 2013-02-03T18:32:04.107 回答