là gì nhanh hơn trong việc tìm kiếm phần tử với tài sản có giá trị tối đa

Question

Thông thường, để tìm phần tử với tài sản có giá trị tối đa tôi làm như thế này

var itemWithMaxPropValue = collection.OrderByDescending(x => x.Property).First(); 

Nhưng là nó theo cách tốt từ thời điểm thực hiện xem? Có lẽ tôi nên làm một cái gì đó như thế này?

var maxValOfProperty = collection.Max(x => x.Property); 
var itemWithMaxPropValue = collection 
           .Where(x => x.Property == maxValueOfProperty).First(); 

Answer 1

Cả hai giải pháp đều không hiệu quả lắm. Giải pháp đầu tiên liên quan đến việc sắp xếp toàn bộ bộ sưu tập. Giải pháp thứ hai đòi hỏi phải vượt qua bộ sưu tập hai lần. Nhưng bạn có thể tìm mục có giá trị thuộc tính tối đa trong một lần mà không cần sắp xếp bộ sưu tập. Có tiện ích mở rộng MaxBy trong thư viện MoreLINQ. Hoặc bạn có thể thực hiện cùng một chức năng:

public static TSource MaxBy<TSource, TProperty>(this IEnumerable<TSource> source, 
    Func<TSource, TProperty> selector) 
{ 
    // check args   

    using (var iterator = source.GetEnumerator()) 
    { 
     if (!iterator.MoveNext())    
      throw new InvalidOperationException(); 

     var max = iterator.Current; 
     var maxValue = selector(max); 
     var comparer = Comparer<TProperty>.Default; 

     while (iterator.MoveNext()) 
     { 
      var current = iterator.Current; 
      var currentValue = selector(current); 

      if (comparer.Compare(currentValue, maxValue) > 0) 
      { 
       max = current; 
       maxValue = currentValue; 
      } 
     } 

     return max; 
    } 
} 

Cách sử dụng rất đơn giản:

var itemWithMaxPropValue = collection.MaxBy(x => x.Property); 

Answer 2

Tôi sẽ đi với Max vì nó được thiết kế đặc biệt cho mục đích đó. Sắp xếp để tìm giá trị Max có vẻ quá nhiều.

Ngoài ra, tôi sẽ không sử dụng Where để tìm số tối đa, nhưng Single - vì những gì chúng tôi cần ở đây là giá trị Single.

var maxValOfProperty = collection.Max(x => x.Property); 
var itemWithMaxPropValue = collection 
          .Single(x => x.Property == maxValueOfProperty); 

Hoặc cách khác sử dụng First (nếu bộ sưu tập chứa bản sao của giá trị tối đa)

var maxValOfProperty = collection.Max(x => x.Property); 
var itemWithMaxPropValue = collection 
          .First(x => x.Property == maxValueOfProperty); 

Hoặc, sử dụng MoreLINQ (theo đề nghị của Kathi), bạn có thể làm điều đó với MaxBy:

var itemWithMaxPropValue = collection.MaxBy(x => x.Property); 

Kiểm tra điều này post, theo trả lời của Jon Skeet.

Answer 3

Phần tử tối đa trong một số chức năng được chỉ định cũng có thể được tìm thấy bằng hai hàm sau.

static class Tools 
{ 
    public static T ArgMax<T, R>(T t1, T t2, Func<T, R> f) 
    where R : IComparable<R> 
    { 
     return f(t1).CompareTo(f(t2)) > 0 ? t1 : t2; 
    } 

    public static T ArgMax<T, R>(this IEnumerable<T> Seq, Func<T, R> f) 
    where R : IComparable<R> 
    { 
     return Seq.Aggregate((t1, t2) => ArgMax<T, R>(t1, t2, f)); 
    } 
} 

Giải pháp trên hoạt động như sau; sự quá tải đầu tiên của ArgMax lấy một bộ so sánh làm đối số để ánh xạ cả hai trường hợp của T thành một loại thực hiện so sánh; số tiền tối đa được trả lại. Sự quá tải thứ hai có một chuỗi như một đối số và chỉ đơn giản là tập hợp hàm đầu tiên. Đây là công thức âm thanh tổng quát, tái sử dụng và cấu trúc nhất cho tìm kiếm tối đa mà tôi biết; tìm kiếm tối thiểu có thể được thực hiện theo cùng một cách bằng cách thay đổi so sánh trong hàm đầu tiên.

Answer 4

Sắp xếp là N * log (N) trong khi Max có N chỉ có thời gian phức tạp, vì vậy Max là nhanh. Những gì bạn đang tìm kiếm là ArgMax chức năng mà LINQ không cung cấp, vì vậy tôi đề nghị thực hiện nó, ví dụ:

public static class EnumerableExtensions { 
    public static T ArgMax<T, K>(this IEnumerable<T> source, 
           Func<T, K> map, 
           IComparer<K> comparer = null) { 
     if (Object.ReferenceEquals(null, source)) 
     throw new ArgumentNullException("source"); 
     else if (Object.ReferenceEquals(null, map)) 
     throw new ArgumentNullException("map"); 

     T result = default(T); 
     K maxKey = default(K); 
     Boolean first = true; 

     if (null == comparer) 
     comparer = Comparer<K>.Default; 

     foreach (var item in source) { 
     K key = map(item); 

     if (first || comparer.Compare(key, maxKey) > 0) { 
      first = false; 
      maxKey = key; 
      result = item; 
     } 
     } 

     if (!first) 
     return result; 
     else 
     throw new ArgumentException("Can't compute ArgMax on empty sequence.", "source"); 
    } 
    } 

Vì vậy, bạn có thể đặt nó chỉ đơn giản

var itemWithMaxPropValue = collection 
    .ArgMax(x => x.Property);