Tại sao IEnumerable chậm và Danh sách nhanh?

Question

Đến qua mã này.

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()) 

Vì vậy, khi .ToList() được nhận xét là chậm, khi không - nhanh. Tái sản xuất here Làm cách nào để giải thích điều này? Tôi có nên luôn làm mọi thứ ToList() để đảm bảo tốc độ (tức là trong trường hợp nào IEnumerable sẽ thích hợp hơn)? Lưu ý tôi đang nói về linq cho các đối tượng, tôi biết linq để sql laziness và các công cụ.

Answer 1

Điều này là do thực thi hoãn lại: khi bạn nhận xét ToList, việc liệt kê được tạo bằng cách đánh giá chuỗi bộ lọc cho mỗi mục trong từ điển. Tuy nhiên, khi bạn thực hiện một số ToList, chuỗi được "vật hoá" trong bộ nhớ, vì vậy tất cả các đánh giá được thực hiện chính xác một lần.

Logic đằng sau thứ hai Where mà không ToList trông như thế này:

// 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); 
    } 
} 

Logic với ToList trông như thế này:

// 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); 
    } 
} 

Như bạn có thể thấy, ToList biến một chương trình O(n^2) với hai vòng lặp lồng nhau có kích thước n thành O(2*n) với hai vòng tuần tự có kích thước là n mỗi vòng.

Answer 2

LINQ sử dụng thực hiện hoãn lại.
Trừ khi bạn gọi .ToList(), kết quả của truy vấn sẽ không bao giờ được lưu trữ ở bất kỳ đâu; thay vào đó, nó lặp lại truy vấn mỗi khi bạn lặp lại kết quả.

Thông thường, điều này nhanh hơn nhiều; thường không có lý do để lưu trữ tất cả các kết quả trong bộ nhớ đầu tiên.

Tuy nhiên, mã của bạn liên tục lặp lại truy vấn; một lần cho mỗi cuộc gọi đến cuộc gọi lại Where().

Bạn nên thay thế dòng đó bằng một cuộc gọi Join() và không ToList(), sẽ nhanh hơn một trong hai cách tiếp cận.

Answer 3

Nguyên nhân là do thực thi hoãn lại. IEnumerable không phải là một bộ sưu tập tĩnh. Generaly nó là một số nguồn dữ liệu (dic trong trường hợp của bạn) + tất cả các phương pháp và biểu thức (ở đâu, Chứa, vv) dẫn đến tập cuối cùng.

. ToList() thực thi tất cả các phương thức và biểu thức này và tạo kết quả cuối cùng.

Vì vậy, trong trường hợp bạn sử dụng ToList() nó tạo ra một danh sách .NET tiêu chuẩn (mảng số nguyên) và thực hiện tất cả các thao tác trên danh sách đó.

Nếu bạn không gọi ToList() (hoặc bất kỳ phương thức nào khác), IEnumerable có thể được liệt kê nhiều lần.

Answer 4

Bởi vì khi bạn không có cuộc gọi .ToList(), instantiation list2 sẽ lặp qua toàn bộ list đếm cho mọi mục trong từ điển. Vì vậy, bạn đi từ O (n) đến O (n^2) nếu bạn sử dụng thực thi hoãn lại.