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）の下限と上限の二分探索によるソートを利用することで、これをはるかに高速に実行できます。

2番目の例-セットのリストに対する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）の1つの大きな並べ替えリストに効果的にジッパーマージできます。リストはすでに並べ替えられているため、結果の.OrderByは無視できます。

代わりに、SelectManyは、ソートされたすべてのセットを1つの大きな（現在はソートされていない）リストに連結します。これには、別のO（n log n）ソートが必要になります。これは、.OrderByを削除し、要素がコンソールに書き込まれる順序を観察することで簡単に確認できます。

私の質問は次のとおりです。SortedSet/SortedListに対するLINQの代替のより効率的な実装はすでにありますか？

i4oは非常に興味深いように見えますが、元のコレクションのクエリパフォーマンスを向上させるには、セカンダリインデックスコレクションが必要なようです。並べ替えを利用して、並べ替えられたコレクションに対するクエリをより高速に実行したいだけです。

4

1 に答える 1

6

LINQの問題は、ソートされたセットがクエリが期待するのとまったく同じ方法で順序付けられていることを認識できないことです。IComparer順序付けられたコレクションは//で作成できるため、実際に意味があるIComparableかComparison<T>どうかはわかりません。> 500000たぶん、最初に奇数/偶数でソートし、次に数値でソートするカスタムメソッドを比較器に持っているかもしれません。その場合、注文は完全に台無しになり、すべての場合にO（n）が必要になります。

したがって、安全のために、LINQは、何らかの方法で並べ替えられている場合でも、コレクション内のすべての要素を反復処理する必要があります。デフォルトの.Where実装には、順序付けされたコレクションの最適化は含まれていません。

反復中に既存の順序を念頭に置いて最適化されたバージョンを作成することは可能かもしれませんが、それを実行してすべての場合に機能させることは非常に困難です。

Betweenのメソッドを使用して、事前に注文した新しいコレクションを返すGetViewBetweenメソッドを作成できます。または、事前に並べ替えられていないセットに対して通常行うようSortedSetに、標準を追加します。.Where

Linq-to-SQLとEntityFrameworkは、IQueryableの場合に使用し、実際にLinqクエリをSQLに変換して、サーバーにインデックス作成、並べ替え、フィルタリングなどを処理させます。

于 2013-02-03T18:32:04.107 に答える