OrderBy and Top in LINQ với hiệu suất tốt

Question

Cách tốt nhất để có được 10 bản ghi hàng đầu từ một bộ sưu tập rất lớn và sử dụng một OrderBy tùy chỉnh là gì? Nếu tôi sử dụng phương thức LINQ to Objects OrderBy thì nó sẽ chậm và mất rất nhiều bộ nhớ vì nó tạo ra một bộ sưu tập hoàn toàn mới với thứ tự mới. Tôi muốn một phương pháp mới với chữ ký bên dưới mà không sắp xếp lại các bộ sưu tập và rất nhanh:

public static IEnumerable<TSource> OrderByTop<TSource, TKey>(
    IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector, 
    IComparer<TKey> comparer, 
    int topCount) 

tôi đã cố gắng để viết nó nhưng nó trở nên rất phức tạp và tôi nghĩ có thể có bất kỳ cách dễ dàng hơn bằng cách sử dụng tổng hợp hoặc một cái gì đó. Bất kỳ trợ giúp sẽ được đánh giá cao.

trả lời

Thanks for the help. Tôi đã kết thúc với đoạn mã sau:

public static List<TSource> OrderByTop<TSource, TKey>(
    this IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector, 
    IComparer<TKey> comparer, 
    int topCount) 
{ 
    var itemComparer = keySelector.ToIComparer(comparer); 
    return source.Aggregate(
     new List<TSource>(topCount), 
     (List<TSource> list, TSource item) => 
      list.SortedInsert(item, itemComparer, topCount)); 
} 

Phương pháp Danh sách mở rộng SortedInsert sau:

public static List<T> SortedInsert<T>(
    this List<T> list, 
    T item, 
    IComparer<T> comparer, 
    int maxLength) 
{ 
    if (list.Count == maxLength) 
     if (comparer.Compare(item, list[maxLength - 1]) >= 0) 
      return list; 
     else 
      list.RemoveAt(maxLength - 1); 
    int insertIndex = list.BinarySearch(item, comparer); 
    if (insertIndex < 0) 
     insertIndex = ~insertIndex; 
    list.Insert(insertIndex, item); 
    return list; 
} 

Đối với những người quan tâm tôi cũng có phương pháp keySelector mở rộng chuyển đổi sang IComparer.

public static IComparer<TSource> ToIComparer<TSource, TKey>(
    this Func<TSource, TKey> keySelector, 
    IComparer<TKey> comparer) 
{ 
    return new KeySelectorToIComparerConverter<TSource, TKey>(
     keySelector, 
     comparer); 
} 
private class KeySelectorToIComparerConverter<TSource, TKey> 
    : IComparer<TSource> 
{ 
    private readonly IComparer<TKey> comparer; 
    private readonly Func<TSource, TKey> keySelector; 
    public KeySelectorToIComparerConverter(
     Func<TSource, TKey> keySelector, 
     IComparer<TKey> comparer) 
    { 
     this.comparer = comparer; 
     this.keySelector = keySelector; 
    } 
    public int Compare(TSource x, TSource y) 
    { 
     return comparer.Compare(keySelector(x), keySelector(y)); 
    } 
} 

Answer 1

Aggregate là một nơi tốt để bắt đầu với:

SortedList<TKey, TSource> resultlist = new SortedList<TKey, TSource>(); 
MyBigList.Aggregate(resultlist, (aktlist,entry) => { 
    aktlist.Add(entry.Key, entry); 
    if (aktlist.Count > 10) aktlist.RemoveAt(10); 
    return aktlist; 
}); 

Nếu bạn muốn có một Comparer khác nhau, bạn có thể chỉ định một trong các nhà xây dựng của SortedList.

EDIT Như đã đề cập bởi nikie, SortedList không thể chứa giá trị kép. Bạn có thể sử dụng một danh sách tiêu chuẩn cùng với BinarySearch để đạt được hiệu quả tương tự:

List<TSource> resultlist = new List<TSource>(); 
MyBigList.Aggregate(resultlist, (aktlist, entry) => { 
    int index = aktlist.BinarySearch(entry); 
    if (index < 0) index = ~index; 
    if (index < 10) aktlist.Insert(index, entry); 
    if (aktlist.Count > 10) aktlist.RemoveAt(10); 
    return aktlist; 
}); 

Một lần nữa một comparer tùy chỉnh (cùng với một lựa chọn tùy chỉnh quan trọng) có thể được sử dụng như là tham số để BinarySearch.

Answer 2

Tôi nghĩ điều bạn muốn thực sự là selection algorithm. Tôi không biết rằng LINQ là cách tốt nhất để thực hiện một kể từ khi tôi nghĩ rằng nó về cơ bản kết thúc như lựa chọn bằng cách phân loại. Bạn phải có khả năng làm điều này trong O (kN), trong đó k là số "hàng đầu" của các mục bằng cách lặp qua bộ sưu tập, theo dõi phần tử "top" tối thiểu được nhìn thấy cho đến nay và nếu phần tử hiện tại lớn hơn thay thế phần tử đó bằng phần tử hiện tại (và cập nhật phần tử tối thiểu mới). Đây là không gian hiệu quả là tốt.

Khi bạn hoàn tất, bạn có thể trả về các phần tử "trên cùng" dưới dạng bộ sưu tập được sắp xếp.

Lưu ý: Tôi giả định LINQ to Objects tại đây. Nếu bạn đang sử dụng LINQ to SQL, thì tôi sẽ trì hoãn đơn giản là trì hoãn việc sắp xếp/lựa chọn đến máy chủ SQL và chỉ cần chuỗi các phương thức thích hợp để có được truy vấn select top N ... from ... order by ....

Hoàn toàn chưa được kiểm tra, thậm chí không được biên soạn. Sử dụng một thực thi Fibonacci Heap chung. Tôi sẽ đăng mã trên blog của tôi (http://farm-fresh-code.blogspot.com) đôi khi sớm. Tôi đã có một treo xung quanh (không chắc chắn nếu nó chung chung) như là kết quả của một số thí nghiệm với hàng đợi ưu tiên mà tôi đã làm. Xem wikipedia để biết thông tin và mã giả cho đến lúc đó.

public static IEnumerable<TSource> OrderByTop<TSource, TKey>(
    IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector, 
    IComparer<TKey> comparer, 
    int topCount) 
{ 
    // allocate enough space to hold the number of elements (+1 as a new candidate is added) 
    FibonacciHeap<TKey,TSource> top = new FibonacciHeap<TKey,TSource>(comparer); 
    foreach (var candidate in source) // O(n) 
    { 
     TKey key = keySelector(candidate); 
     TKey minimum = top.AccessMinimum(); 
     if (minimum == null || comparer.Compare(key, minimum.Key) > 0) // O(1) 
     { 
      top.Insert(key, candidate); // O(1) 
      if (top.Count >= topCount) 
      { 
       top.DeleteMinimum(); // O(logk) 
      } 
     } 
    } 
    return top.ToList().Reverse().Select(t.Value); // O(k) 
} 

Answer 3

Tôi không biết giải pháp nào khác ngoài việc viết phương pháp này. Tuy nhiên phương pháp này không phải là phức tạp.

Bạn cần phải duy trì danh sách được sắp xếp với 10 yếu tố hàng đầu và lặp qua bộ sưu tập orinigal một lần.

Nếu bản ghi hiện tại trong quá trình lặp lại nhỏ hơn bản ghi cuối cùng trong danh sách 10 hàng đầu hoặc khi bạn chưa có 10 bản ghi đầu tiên, thì bạn phải thêm mục vào danh sách này. (Và tất nhiên, hãy xóa mục cuối cùng khỏi danh sách 10 hàng đầu, khi thích hợp.)

Answer 4

Bạn cũng có thể triển khai thuật toán sắp xếp phân chia và chinh phục như quicksort và ngắt ngay sau khi bạn có k yếu tố được sắp xếp đầu tiên. Nhưng đề xuất của tvanfosson có thể nhanh hơn nếu k < < N