问优化自然排序序列的Join、GroupBy、Distinct、Min/Max
EN

Stack Overflow用户

提问于 2011-02-07 23:47:03

回答 4查看 315关注 0票数 3

LINQ运算符基于输入序列未排序的假设进行操作，这对于一般情况很有用。但是，如果源序列是按键值排序的，则上述操作符可能会更有效。

例如，Join将整个内部序列读取到哈希表中，然后才对外部序列进行迭代。如果对两个序列进行排序，则可以将Join实现为简单的合并，而无需额外的存储和哈希表查找。

有没有一个库可以替代高性能的LINQ函数来操作预先排序的序列？

.net

linq-to-objects

回答 4

Stack Overflow用户

回答已采纳

发布于 2011-02-08 01:00:10

我开发Nito.LINQ是因为我有时间。它为ISortedEnumerable和ISortedList提供了您建议的一些优化。我还包括了更多有争议的优化(例如，针对IList的Skip，它稍微改变了语义)。

票数 0

Stack Overflow用户

发布于 2011-02-08 00:06:45

可以，但不适用于LINQ to Objects。大多数在IQueryable<T>上工作的LINQ提供程序已经将其转换为“本机”函数，该函数可以很容易地实现这种类型的优化。例如，当使用Entity Framework时，EF提供程序会将其转换为SQL调用，而DB (希望如此)会正确地对其进行优化。

不过，LINQ to Objects稍有不同。在那里，大多数例程(包括上面的所有例程)都被设计为处理未排序的数据，甚至是IEqualityComparer<T>或IComparer<T>的不同实现。这意味着“优化”版本不仅适用于一小部分潜在数据，而且只针对标准查询操作的一个子集进行优化。

也就是说，对于那些特定的情况，使用自己的包装器对标准LINQ操作进行封装是相当容易的。但是，您需要一种方法来提前知道有问题的集合是否已排序，这可能需要您自己的单独接口(或运行时检查，如在ICollection上进行的Count()优化)。

票数 0

Stack Overflow用户

发布于 2011-02-08 00:55:42

正如Reed提到的，为了确定优化是否有效，很难发现序列是按什么排序的。您不会真的希望必须滚动重复的集合类，或者将自己绑定到特定的实现(如IOrderedEnumerable<T>)，以编写LINQ扩展方法的覆盖。

那么，如果只是添加一些新的运算符或重载，您作为消费者可以保证数据是有序的，那会怎么样呢？这些仍然可以是IEnumerable<T>上的扩展方法，除非对集合进行排序，否则不能保证成功。

一个例子是OrderedJoin，您必须提供一个IComparable<TKey>，以便知道如果每个序列中的当前项与键不匹配，则下一步前进哪个序列。这是作为开场白的签名。你可以让我们知道你什么时候实现了你的整个库！

public static IEnumerable<TResult> OrderedJoin<TOuter, TInner, TKey, TResult>(
    this IEnumerable<TOuter> outer,
    IEnumerable<TInner> inner,
    Func<TOuter, TKey> outerKeySelector,
    Func<TInner, TKey> innerKeySelector,
    Func<TOuter, TInner, TResult> resultSelector,
    IComparable<TKey> comparer
)