tra cứu từ điển (O (1)) vs LINQ nơi

Question

Nhanh hơn và tôi nên hy sinh tiêu chuẩn LINQ để đạt được tốc độ (giả sử tra cứu từ điển thực sự nhanh hơn) là gì? Vì vậy, hãy để tôi giải thích:

Tôi đã điều sau đây:

List<Product> products = GetProductList(); 

tôi có nhu cầu tìm kiếm một sản phẩm dựa trên một số thuộc tính, ví dụ, số serial. đầu tiên tôi có thể tạo ra một từ điển, và sau đó cư nó như sau:

Dictionary<string, Product> dict = new Dictionary<string, Product>(); 
foreach(Product p in products) 
{ 
    dict.Add(p.serial, p); 
} 

Khi đó là thời gian để tìm một sản phẩm, tận dụng lợi thế của O (1) được cung cấp bởi nhìn lên từ điển:

string some_serial = ...; 
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { } 

Ngoài ra, sử dụng LINQ:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault(); 

Hạn chế với cách tiếp cận Dict là tất nhiên điều này đòi hỏi nhiều không gian hơn trong bộ nhớ, nhiều mã để viết, ít thanh lịch, vv (mặc dù hầu hết trong số này là gây tranh cãi). Giả sử đó không phải là yếu tố. Tôi có nên sử dụng cách tiếp cận đầu tiên không?

Để kết luận, tôi muốn xác nhận xem mức độ phức tạp của phương pháp tiếp cận LINQ ở trên thực sự là O (n) và tôi không thấy nó có thể tốt hơn thế nào.

Answer 1

Giả sử bạn đang bắt đầu với một điều tra các đối tượng và chỉ đang làm điều này một lần ...

Nó sẽ nhanh hơn để làm phương pháp Where như trái ngược với việc thêm vào một Dictionary<TKey,TValue> và sau đó tìm kiếm nó lại lên. Lý do tại sao phương pháp từ điển là không phải là O (1). Trong trường hợp này, bạn đang thêm các mục vào từ điển và sau đó tìm kiếm nó. Phần bổ sung là O (N) đắt tiền như phương pháp Where với chi phí bộ nhớ bổ sung.

Một điểm nhỏ khác cần lưu ý là Dictionary<TKey,TValue> không thực sự là O (1). Thay vào đó nó tiếp cận O (1) nhưng có thể làm suy giảm hiệu suất thấp hơn trong một số trường hợp nhất định (ví dụ như rất nhiều phím xung đột).