自然にソートされたシーケンスのJoin、GroupBy、Distinct、Min/Maxを最適化する

Question

LINQ演算子は、入力シーケンスがソートされていないことを前提として動作します。ただし、ソースシーケンスがキー値でソートされている場合は、上記の演算子が効率的になる可能性があります。

たとえば、Joinは内部シーケンス全体をハッシュテーブルに読み込み、その後にのみ外部シーケンスを反復処理します。 2つのシーケンスがソートされている場合、Joinは、追加のストレージおよびハッシュテーブルルックアップを使用しない単純なマージとして実装できます。

事前ソートされたシーケンスで動作する代替の高性能LINQ関数を持つライブラリはありますか？

Answer 1

私は時間があるのでNito.LINQを開発します。提案する最適化の一部をISortedEnumerableとISortedListに提供しています。さらに議論の余地がある最適化も含まれています（例：の場合はSkip、セマンティクスはわずかです）。

Answer 2

はい、LINQ to Objectsはありません。 IQueryable<T>で動作するほとんどのLINQプロバイダは、この種の最適化を簡単に実行できる「ネイティブ」関数への変換を既に行っています。たとえば、Entity Frameworkを使用している場合、EFプロバイダはこれをSQL呼び出しに変換し、DB（うまくいけば）がこれを正しく最適化します。

LINQ to Objectsは少し異なりますが、そこでは、上記のすべてを含むルーチンのほとんどは、ソートされていないデータ、さらにIEqualityComparer<T>またはIComparer<T>の異なる実装でも動作するように設計されています。これは、「最適化された」バージョンが、潜在的なデータの小さなセットに対してのみ機能するだけでなく、標準的なクエリ操作のサブセットに対してのみ最適化されることを意味する。

言われているように、これらの特定のケースでは、標準のLINQ操作の周りに独自のラッパーを使用してこれを行うのはかなり簡単でしょう。しかし、事前に、問題のコレクションがソートされていることを事前に知っておく必要があります。これは、おそらく独自の別のインターフェイス（またはCount()ICollectionで行われた最適化のようなランタイムチェック）を必要とします。

Answer 3

Reedが述べているように、最適化が機能するかどうかを判断するために、配列をソートしたものを発見することは非常に困難です。重複したコレクションクラスをロールバックしたり、LINQ拡張メソッドのオーバーライドを書き込むために、具体的な実装（例えばIOrderedEnumerable<T>など）に自分自身を結びつける必要はありません。

したがって、消費者がデータの注文を保証する新しいオペレータまたはオーバーロードを追加するだけでどうでしょう。これらは依然として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 
) 

Answer 4

using System; 
using System.Collections; 
using System.Collections.Generic; 
using System.Linq; 

namespace OrderedJoin 
{ 
    public static class EnumerableExtension 
    { 
     private enum JoinType 
     { 
      Inner, 
      Left, 
      Right, 
      Full 
     } 

     private static IEnumerable<TResult> OrderedJoinIterator<T, TResult>(
      this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, JoinType jt, IComparer<T> comparer) 
     { 
      if (left == null) throw new ArgumentNullException("left"); 
      if (right == null) throw new ArgumentNullException("right"); 
      if (resultSelector == null) throw new ArgumentNullException("resultSelector"); 

      if (comparer == null) 
       comparer = Comparer<T>.Default; 

      var l = left.GetEnumerator(); 
      var r = right.GetEnumerator(); 

      var lHasData = l.MoveNext(); 
      var rHasData = r.MoveNext(); 

      while (lHasData || rHasData) 
      { 
       if (!lHasData && rHasData) 
       { 
        if (jt == JoinType.Inner || jt == JoinType.Left) 
         yield break; 
        yield return resultSelector(default(T), r.Current); 
        rHasData = r.MoveNext(); 
        continue; 
       } 
       if (!rHasData && lHasData) 
       { 
        if (jt == JoinType.Inner || jt == JoinType.Right) 
         yield break; 
        yield return resultSelector(l.Current, default(T)); 
        lHasData = l.MoveNext(); 
        continue; 
       } 

       var comp = comparer.Compare(l.Current, r.Current); 

       if (comp < 0) 
       { 
        if (jt == JoinType.Left || jt == JoinType.Full) 
         yield return resultSelector(l.Current, default(T)); 
        lHasData = l.MoveNext(); 
       } 
       else if (comp > 0) 
       { 
        if (jt == JoinType.Right || jt == JoinType.Full) 
         yield return resultSelector(default(T), r.Current); 
        rHasData = r.MoveNext(); 
       } 
       else 
       { 
        yield return resultSelector(l.Current, r.Current); 
        lHasData = l.MoveNext(); 
        rHasData = r.MoveNext(); 
       } 
      } 
     } 

     public static IEnumerable<TResult> OrderedInnerJoin<T, TResult>(
      this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null) 
     { 
      return OrderedJoinIterator(left, right, resultSelector, JoinType.Inner, comparer); 
     } 

     public static IEnumerable<TResult> OrderedFullJoin<T, TResult>(
      this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null) 
     { 
      return OrderedJoinIterator(left, right, resultSelector, JoinType.Full, comparer); 
     } 

     public static IEnumerable<TResult> OrderedLeftJoin<T, TResult>(
      this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null) 
     { 
      return OrderedJoinIterator(left, right, resultSelector, JoinType.Left, comparer); 
     } 

     public static IEnumerable<TResult> OrderedRightJoin<T, TResult>(
      this IEnumerable<T> left, IEnumerable<T> right, Func<T, T, TResult> resultSelector, IComparer<T> comparer = null) 
     { 
      return OrderedJoinIterator(left, right, resultSelector, JoinType.Right, comparer); 
     } 
    } 

    internal class TestEnum : IEnumerable<int> 
    { 
     public TestEnum(string name, IList<int> nums) 
     { 
      Name = name; 
      Nums = nums; 
     } 

     public string Name { get; private set; } 
     public IList<int> Nums { get; private set; } 

     public IEnumerator<int> GetEnumerator() 
     { 
      foreach (var item in Nums) 
      { 
       Console.WriteLine("{0}: {1}", Name, item); 
       yield return item; 
      } 
     } 

     IEnumerator IEnumerable.GetEnumerator() 
     { 
      return GetEnumerator(); 
     } 
    } 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      var e1 = new TestEnum("L", new List<int> { 1, 2, 5, 6 }); 
      var e2 = new TestEnum("R", new List<int> { 1, 3, 4, 6 }); 

      var print = new Action<IEnumerable<string>>(seq => { foreach (var item in seq) Console.WriteLine("\t" + item); }); 

      Console.WriteLine("Standard Inner Join:"); 
      print(e1.Join(e2, i => i, j => j, (i, j) => string.Format("{0} <=> {1}", i, j), EqualityComparer<int>.Default)); 

      Console.WriteLine("Ordered Inner Join:"); 
      print(e1.OrderedInnerJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j))); 

      Console.WriteLine("Ordered Full Join:"); 
      print(e1.OrderedFullJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j))); 

      Console.WriteLine("Ordered Left Join:"); 
      print(e1.OrderedLeftJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j))); 

      Console.WriteLine("Ordered Right Join:"); 
      print(e1.OrderedRightJoin(e2, (i, j) => string.Format("{0} <=> {1}", i, j))); 

      Console.ReadLine(); 
     } 
    } 
}