20

このコードに出くわしました。

var dic = new Dictionary<int, string>();
for(int i=0; i<20000; i++)
{
    dic.Add(i, i.ToString());
}

var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key);//.ToList(); //uncomment for fast results 
Console.WriteLine(list.GetType());
var list2 = dic.Where(f => list.Contains(f.Key)).ToList();
Console.WriteLine(list2.Count());

したがって、 .ToList() がコメントされている場合は遅く、コメントされていない場合は高速です。ここで再現可能これはどのように説明できますか? 速度を確保するために、常にすべてを ToList() にする必要がありますか (つまり、どのような状況で IEnumerable がより望ましいか)? 私はオブジェクトへのlinqについてのみ話していることに注意してください.linq to sqlの怠惰などを知っています。

4

4 に答える 4

29

これは遅延実行によるものです。コメント アウトするToListと、辞書内の各項目の一連のフィルターを評価することによって列挙が生成されます。ただし、を実行するToListと、シーケンスはメモリ内で「実体化」されるため、すべての評価が 1 回だけ実行されます。

Where2 番目のwithoutの背後にあるロジックはToList次のようになります。

// The logic is expanded for illustration only.
var list2 = new List<KeyValuePair<int,string>>();
foreach (var d in dict) {
    var list = new List<int>();
    // This nested loop does the same thing on each iteration,
    // redoing n times what could have been done only once.
    foreach (var f in dict) {
        if (f.Value.StartsWith("1")) {
            list.Add(f.Key);
        }
    }
    if (list.Contains(d.Key)) {
        list2.Add(d);
    }
}

のロジックはToList次のようになります。

// The list is prepared once, and left alone
var list = new List<int>();
foreach (var f in dict) {
    if (f.Value.StartsWith("1")) {
        list.Add(f.Key);
    }
}
var list2 = new List<KeyValuePair<int,string>>();
// This loop uses the same list in all its iterations.
foreach (var d in dict) {
    if (list.Contains(d.Key)) {
        list2.Add(d);
    }
}

ご覧のとおり、 は、サイズのネストされた 2 つのループを持つプログラムを、それぞれサイズの 2 つの順次ループを持つプログラムに変換ToListします。O(n^2)nO(2*n)n

于 2013-10-30T17:07:59.910 に答える
14

LINQ は遅延実行を使用します。
を呼び出さない限り.ToList()、クエリの結果はどこにも保存されません。代わりに、結果を繰り返すたびにクエリを繰り返します。

通常、これははるかに高速です。通常、最初にすべての結果をメモリに格納する理由はありません。

ただし、コードはクエリを繰り返し繰り返します。コールバックへの呼び出しごとに 1 回Where()。

Join()その行をcall と noに置き換える必要がToList()あります。これは、どちらのアプローチよりも高速です。

于 2013-10-30T17:08:01.177 に答える
3

.ToList()呼び出しがない場合、インスタンス化はディクショナリ内のすべての項目に対して列挙可能なlist2全体を反復処理するためです。listしたがって、遅延実行を使用すると、O(n) から O(n^2) になります。

于 2013-10-30T17:22:58.877 に答える
2

遅延実行が原因です。IEnumerable は静的コレクションである必要はありません。一般的に、最終的なセットにつながるのは、いくつかのデータソース（dicあなたの場合）+すべてのメソッドと式（Where、Containsなど）です。

.ToList() は、これらすべてのメソッドと式を実行し、最終結果を生成します。

したがって、ToList() を使用すると、標準の .NET リスト (整数の配列) が生成され、そのリストに対してすべての操作が実行されます。

ToList() (またはその他の To メソッド) を呼び出さない場合、IEnumerable を複数回列挙できます。

于 2013-10-30T17:11:58.393 に答える