मैक्स() बनाम ऑर्डरबैडस्केंडिंग()। पहला()

Question

यह पूरी तरह से मेरे अपने ज्ञान के लिए है, अगर मैं कोड लिखने जा रहा हूं तो मैं केवल .Max() का उपयोग करूंगा।

पहले विचार पर .Max() को अधिकतम खोजने के लिए केवल numbers के माध्यम से एक ही पास करना होगा, जबकि दूसरी तरफ पूरी चीज को समेकित करना होगा, फिर पहले को ढूंढें। तो यह O(n) बनाम O(n lg n) है। लेकिन फिर मैं सोच रहा था कि शायद यह जानता है कि इसे केवल उच्चतम की जरूरत है और बस इसे पकड़ लेता है।

प्रश्न: है LINQ और/या संकलक बहुत चालाक यह पता लगाने की है कि यह पूरे गणनीय सॉर्ट करने के लिए और() की जरूरत नहीं है .max के रूप में मूलतः एक ही करने के लिए नीचे कोड फोड़े? क्या पता लगाने के लिए एक मात्रात्मक तरीका है?

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

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

Answer 1

यदि आप सीधे LINQ से ऑब्जेक्ट्स के बारे में बात कर रहे हैं, तो नहीं, यह इसके लिए अनुकूल नहीं है।

संभवतः एक और LINQ प्रदाता कर सकता है, लेकिन यह कार्यान्वयन के विवरण पर निर्भर करता है।

Enumerable के लिए, कार्यान्वयन कि परावर्तक मुझे देता हैं:

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

और 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() हे (एन) है, जबकि अपनी OrderByDescending समाधान नहीं है - प्रकार पर निर्भर करता है, यह शायद हे है (nlog (एन))।

मैंने स्पष्ट रूप से संकलक के अंदर खोदने के लिए खोला नहीं है, लेकिन आप जो पूछ रहे हैं (एक अनुकूलन जो सॉर्ट को समझता है, फिर केवल एक आइटम को पकड़ लेता है। मैक्स जैसा ही है) एक कंपाइलर से बहुत कुछ है।

Answer 3

के लिए LINQ और/या संकलक बहुत चालाक यह पता लगाने की है कि यदि ऐसा नहीं होता है संपूर्ण गणना करने की आवश्यकता है और कोड को अनिवार्य रूप से उसी तरह उबालता है जैसे मैक्स()?

सं

वहाँ पता लगाने के लिए एक मात्रात्मक रास्ता नहीं है?

स्टॉपवॉच के साथ एक सरल बेंचमार्क:

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); 

मैक्स(): 70ms

OrderBy(): 2066ms

इसके अलावा, OrderBy() एक OutOfMemoryException के साथ विफल हो अगर आप संख्या में वृद्धि उससे बहुत अधिक, मैक्स() नहीं करता है।

Answer 4

ऐसा प्रतीत होता है कि ऑर्डर्डअन्यूमेबल अब यह समझने के लिए पर्याप्त स्मार्ट है कि इसे पहले और अंतिम() के लिए सूची को सॉर्ट करने की आवश्यकता नहीं है।

नोट लाइन 223, TryGetFirst() https://github.com/dotnet/corefx/blob/ed0ee133ac49cee86f10ca4692b1d72e337bc012/src/System.Linq/src/System/Linq/OrderedEnumerable.cs