LINQ to Objects và cải thiện perf với chỉ mục?

Question

Tôi đang sử dụng LINQ to Objects và tự hỏi liệu có thể cải thiện hiệu suất truy vấn của tôi bằng cách sử dụng chỉ mục mà tôi có. Điều này được giải thích tốt nhất với một ví dụ. Hãy tưởng tượng một kiểu đơn giản ...

public class Person 
{ 
    public int Age; 
    public string FirstName; 
    public string LastName; 
} 

Và một truy vấn đơn giản, tôi sẽ làm cho chống lại nó ...

List<Person> people = new List<Person>(); 

// 'people' populated with 50,000 instances... 

var x = from t in people 
     where t.Age > 18 && t.Age < 21 
     select t; 

Nếu tôi hiểu LINQ to Objects một cách chính xác sau đó thực hiện các trường hợp phương pháp khuyến nông sẽ liệt kê tất cả 50.000 trường hợp trong bộ sưu tập người để tìm 100 thực sự phù hợp. Khi điều đó xảy ra, tôi đã có chỉ mục của bộ sưu tập người được sắp xếp theo Độ tuổi. Như thế này ...

SortedList<int, Person> ageSorted = new SortedList<int, Person>(); 

Rõ ràng nó sẽ có ý nghĩa nếu tôi có thể có được ở đâu để sử dụng SortedList để nó không còn phải liệt kê tất cả 50.000 trường hợp, thay vì tìm kiếm khoảng 100 mục tương ứng và do đó tiết kiệm thời gian.

Có thể mở rộng LINQ to Objects để kích hoạt tình huống của tôi không? Là nó đã có thể nhưng tôi thiếu kỹ thuật?

Answer 1

Đã có một dự án mà tôi tin thực hiện chính xác điều đó - i4o. Tôi không thể nói rằng tôi đã sử dụng nó bản thân mình, nhưng nó có vẻ giống như loại điều bạn muốn ... bạn có thể cần phải sắp xếp mã hiện tại của bạn một chút, nhưng nó chắc chắn đáng xem.

Nếu điều đó không trợ giúp, bạn ít nhất có thể viết các phương pháp mở rộng của riêng mình trên SortedList<TKey, TValue>. Có thể bạn sẽ không thể dễ dàng sử dụng mệnh đề where thực tế của mình, nhưng bạn có thể sử dụng các phương pháp của riêng mình với giá trị tối thiểu và tối đa. Bạn có thể cũng muốn đặt chúng áp dụng cho IList<T> nơi bạn khẳng định rằng bạn đã sắp xếp các giá trị phù hợp (theo một số so sánh).

Ví dụ (hoàn toàn chưa được kiểm tra):

public static IEnumerable<T> Between<T, TKey>(this IList<T> source, 
               Func<T, TKey> projection, 
               TKey minKeyInclusive, 
               TKey maxKeyExclusive, 
               IComparer<TKey> comparer) 
{ 
    comparer = comparer ?? Comparer<TKey>.Default; 

    // TODO: Find the index of the lower bound via a binary search :) 
    // (It's too late for me to jot it down tonight :) 
    int index = ...; // Find minimum index 

    while (index < source.Count && 
      comparer.Compare(projection(source[index]), maxKeyExclusive) < 0) 
    { 
     yield return source[index]; 
     index++; 
    } 
} 

(Nếu bạn chỉ có List<T> thay vì IList<T>, bạn có thể sử dụng List<T>.BinarySearch, mặc dù bạn sẽ cần phải xây dựng một tùy chỉnh IComparer<T>.)

Cũng , hãy xem SortedSet<T> trong .NET 4.

Answer 2

Cú pháp truy vấn LINQ thực sự sử dụng bất kỳ phương pháp tiện ích nào có tên Where khớp với chữ ký, vì vậy bạn có thể alwa ys viết của riêng bạn xử lý loại cụ thể theo cách bạn muốn.

public static IEnumerable<Person> Where(this IEnumerable<Person> collection, Func<Person, bool> condition) 
    { 
     Console.WriteLine("My Custom 'Where' method called"); 
     return System.Linq.Enumerable.Where(collection, condition); 
    } 

...

 var x = from t in people 
       where t.Age > 18 && t.Age < 21 
       select t; //Will print "My Custom 'Where' method called" 

Sau đó, bạn có thể áp dụng bất kỳ logic bạn muốn. Tôi tin rằng các quy tắc quá tải phương thức bình thường được áp dụng để xác định phương thức mở rộng nào sẽ được gọi là Where.

Answer 3

Bạn nói đúng rằng truy vấn bạn đã viết sẽ liệt kê toàn bộ danh sách như rõ ràng LINQ không thể giả định bất cứ điều gì về dữ liệu của bạn.

Nếu bạn có một SortedList, bạn có thể khai thác rằng việc sử dụng các phương pháp LINQ SkipWhile/TakeWhile:

var x = x.SkipWhile(kv => kv.Key <= 18).TakeWhile(kv => kv.Key < 21) 

EDIT

@ Davy8 là đúng tất nhiên là trường hợp xấu nhất vẫn này có hiệu suất tương tự. Xem các câu trả lời khác cho một cách để tìm nhanh hơn giá trị đầu tiên.

Nếu bạn cần phải làm nhiều hơn nữa hoạt động này nhiều lần cho độ tuổi khác nhau thì có thể bạn cũng có thể tăng tốc độ nó lên bằng cách nhóm theo độ tuổi:

var byAge = people.GroupBy(p => p.Age); 

var x = from grp in byAge 
     where grp.Key > 18 && grp.Key < 21 
     from person in grp 
     select person; 

Answer 4

Trong một container trước sắp xếp, hiệu quả đạt được bằng cách tìm nhanh nguyên tố đầu tiên. Khi bạn tìm thấy phần tử đầu tiên, chỉ cần truy lục trực tiếp các phần tử sau cho đến khi bạn tìm thấy kết thúc phạm vi của mình.

Giả sử SortedList của bạn được sắp xếp theo Person.Age, bạn có thể tìm phần tử đầu tiên của dải ô bằng cách sử dụng SortedList.IndexOfKey, là một thuật toán binary search; do đó, phương pháp này là một hoạt động O (log n).

(Tôi không nghĩ rằng bạn có thể thay đổi mã của bạn để Enumerable.Where đột nhiên trở nên thông minh hơn và tìm thấy sự khởi đầu loạt bằng cách sử dụng tìm kiếm nhị phân.)

--- EDIT ---

Thực ra, những gì bạn thực sự cần là List.BinarySearch hoặc Array.BinarySearch. SortedList.IndexOfKey sẽ không cho phép bạn lấy chỉ mục của đối sánh gần nhất trong trường hợp khớp chính xác không tồn tại. Hoặc bạn chỉ có thể tự mình thực hiện tìm kiếm nhị phân.