.Max() vs OrderByDescending(). Đầu tiên()

Question

Đây hoàn toàn là kiến ​​thức của riêng tôi, nếu tôi định viết mã, tôi chỉ sử dụng .Max().

Lúc đầu suy nghĩ .Max() chỉ cần thực hiện một lần đi qua numbers để tìm giá trị tối đa, còn cách thứ hai phải sắp xếp toàn bộ nội dung đếm được rồi tìm số đầu tiên. Vì vậy, nó là O(n) và O(n lg n). Nhưng sau đó tôi đã suy nghĩ có lẽ nó biết nó chỉ cần cao nhất và chỉ lấy nó.

Câu hỏi: là LINQ và/hoặc trình biên dịch đủ thông minh để hình dung ra rằng nó không cần phải sắp xếp toàn bộ đếm được và sôi mã xuống cơ bản giống như MAX()? Có cách nào để định lượng được không?

IEnumerable<int> numbers = Enumerable.Range(1, 1000); 

int max = numbers.Max(); 
int max2 = numbers.OrderByDescending(x => x).First(); 

Answer 1

Nếu bạn đang nói về LINQ to Objects thẳng, thì không, nó không tối ưu hóa cho điều đó.

Có lẽ một nhà cung cấp LINQ khác có thể làm, nhưng đó là tùy thuộc vào các chi tiết cụ thể của việc triển khai.

Đối Enumerable, việc triển khai mà Reflector mang lại cho tôi là:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) 
{ 
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false); 
} 

và cho First()

public static TSource First<TSource>(this IEnumerable<TSource> source) 
{ 
    if (source == null) 
    { 
     throw Error.ArgumentNull("source"); 
    } 
    IList<TSource> list = source as IList<TSource>; 
    if (list != null) 
    { 
     if (list.Count > 0) 
     { 
      return list[0]; 
     } 
    } 
    else 
    { 
     using (IEnumerator<TSource> enumerator = source.GetEnumerator()) 
     { 
      if (enumerator.MoveNext()) 
      { 
       return enumerator.Current; 
      } 
     } 
    } 
    throw Error.NoElements(); 
} 

Answer 2

.Max() là O (n), trong khi giải pháp OrderByDescending của bạn không phải là - tùy theo loại, nó có thể là O (nlog (n)). Tôi rõ ràng là không đào sâu bên trong trình biên dịch để biết, nhưng những gì bạn đang yêu cầu (một tối ưu hóa nhận ra sắp xếp sau đó lấy chỉ một mục là giống như .max) là khá nhiều từ một trình biên dịch.

Answer 3

là LINQ và/hoặc trình biên dịch đủ thông minh để hình dung ra rằng nó không cần phải sắp xếp toàn bộ enumerable và boils mã xuống về cơ bản giống như .Max()?

số

Có cách nào định lượng để tìm hiểu?

Một benchmark đơn giản với Stopwatch:

var numbers = Enumerable.Range(1, 10000000); 
    var sw = Stopwatch.StartNew(); 
    int max = numbers.Max(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    sw.Restart(); 
    int max2 = numbers.OrderByDescending(x => x).First(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 

Max(): 70ms

OrderBy(): 2066ms

Ngoài ra, OrderBy() không thành công với một OutOfMemoryException nếu bạn tăng số lượng quá nhiều hơn thế, Max() thì không.

Answer 4

Dường như OrderedEnumerable hiện đủ thông minh để tìm ra rằng nó không cần phải sắp xếp danh sách đầu tiên và cuối cùng().

Note mã vào khoảng dòng 223, TryGetFirst() https://github.com/dotnet/corefx/blob/ed0ee133ac49cee86f10ca4692b1d72e337bc012/src/System.Linq/src/System/Linq/OrderedEnumerable.cs