14

LINQ クエリのパフォーマンスに問題があるため、以下の問題を示すために簡単な例を作成しました。このコードは、小さい整数のランダムなリストを受け取り、合計が 10 以下のいくつかの小さなリストに分割されたリストを返します。

問題は、(私がこれを書いたように) コードが N で指数関数的に長くかかることです。これは O(N) の問題にすぎません。N=2500 の場合、私の PC でコードを実行するには 10 秒以上かかります。

誰かが何が起こっているのかを説明できれば、私は大いに感謝します。ありがとう、マーク。

int N = 250;
Random r = new Random();
var work = Enumerable.Range(1,N).Select(x => r.Next(0, 6)).ToList();
var chunks = new List<List<int>>();

// work.Dump("All the work.");  // LINQPad Print
var workEnumerable = work.AsEnumerable();

Stopwatch sw = Stopwatch.StartNew();
while(workEnumerable.Any())  // or .FirstorDefault() != null
{
    int soFar = 0;
    var chunk = workEnumerable.TakeWhile( x => 
                          {
                              soFar += x;               
                              return  (soFar <= 10);
                          }).ToList();
    chunks.Add(chunk);          // Commented out makes no difference.
    workEnumerable = workEnumerable.Skip(chunk.Count); // <== SUSPECT
}
sw.Stop();

// chunks.Dump("Work Chunks.");   // LINQPad Print
sw.Elapsed.Dump("Time elapsed.");
4

3 に答える 3

11

ソースをループするnewを.Skip()作成し、最初の要素IEnumerableの後にのみ結果を生成し始めます。Nあなたは、これらがいくつあるかを知っている人を連鎖させます。を呼び出すたび.Any()に、以前にスキップしたすべての要素を再度ループする必要があります。

一般的に言えば、LINQ で非常に複雑な演算子チェーンを設定し、それらを繰り返し列挙することはお勧めできません。また、LINQ はクエリ API であるSkip()ため、達成しようとしていることがデータ構造の変更に相当する場合、次のようなメソッドは不適切な選択です。

于 2012-11-20T23:12:34.277 に答える
5

Skip() を同じ列挙型に効果的にチェーンし続けます。250 のリストでは、最後のチャンクは、前面に ~25 の「スキップ」列挙子クラスを持つ遅延列挙型から作成されます。

すでに実行していれば、物事がはるかに高速になることがわかります

workEnumerable = workEnumerable.Skip(chunk.Count).ToList();

ただし、全体のアプローチは変更できると思います。

同じことを達成するために標準のLINQを使用するのはどうですか:

http://ideone.com/JIzpmlで​​ライブをご覧ください

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

public class Program
{
    private readonly static Random r = new Random();

    public static void Main(string[] args)
    {
        int N = 250;
        var work = Enumerable.Range(1,N).Select(x => r.Next(0, 6)).ToList();

        var chunks = work.Select((o,i) => new { Index=i, Obj=o })
            .GroupBy(e => e.Index / 10)
            .Select(group => group.Select(e => e.Obj).ToList())
            .ToList();

        foreach(var chunk in chunks)
            Console.WriteLine("Chunk: {0}", string.Join(", ", chunk.Select(i => i.ToString()).ToArray()));
    }
}
于 2012-11-20T23:13:17.903 に答える
2

メソッドとそれに類するものは、基本的に、IEnumerable を実装するプレースホルダー オブジェクトを作成します。Skip()これは、その親の列挙型を参照し、スキップを実行するロジックを含みます。したがって、ループ内のスキップは、列挙可能な要素を破棄する代わりに、実際に最初の要素が必要なときに遅延実行されるロジックの新しいレイヤーを追加するため、パフォーマンスが低下します。スキップしました。

ToList()またはを呼び出すことで、これを回避できますToArray()。これにより、メソッドの「熱心な」評価が強制Skip()され、列挙する新しいコレクションからスキップしている要素が実際に削除されます。これにはメモリ コストの増加が伴い、すべての要素を把握しておく必要があります (したがってIEnumerable、無限級数を表す でこれを実行している場合は、幸運を祈ります)。

2 番目のオプションは、Linq を使用せず、代わりにIEnumerable実装自体を使用して、IEnumerator. 次に、の代わりに、必要な回数Skip()だけ呼び出します。MoveNext()

于 2012-11-21T00:11:35.220 に答える