सूची <T> सूची के लिए अंतिम() एक्सटेंशन विधि का प्रदर्शन क्या है?

Question

मुझे वास्तव में Last() पसंद है और List<T> s के लिए हर समय इसका उपयोग करेगा। लेकिन चूंकि इसे IEnumerable<T> के लिए परिभाषित किया गया है, मुझे लगता है कि यह पहले गणना को दर्शाता है - यह ओ (एन) के विपरीत होना चाहिए (0) List<T> के अंतिम तत्व को सीधे अनुक्रमणित करने के लिए।

क्या मानक (लिंक) एक्सटेंशन विधियां इस बारे में जागरूक हैं?

सी ++ में एसटीएल इसके बारे में जागरूक और व्हाट्नॉट के लिए पूरे "विरासत पेड़" के आधार पर इसके बारे में पता है।

Answer 1

मैं सिर्फ परावर्तक इस्तेमाल किया अंतिम के लिए कोड की जांच के लिए और यह अगर यह होता है एक IList<T> पहले देखने के लिए जाँच करता है और उचित हे करता है (1) कॉल:

---

संपादित करें:

मेरे वकील की सलाह पर मैंने परावर्तक से कोड स्निपेट हटा दिया है। यदि आप अपने लिए कोड देखना चाहते हैं तो मेरा सुझाव है कि आप या तो परावर्तक प्राप्त करें और इसे स्वयं करें (जो सभी को पहले से ही होना चाहिए) या अधिक आसानी से इस पोस्ट के संशोधन इतिहास में देखें (क्योंकि इसके बारे में मैं कुछ भी नहीं कर सकता)

(या वास्तव में मार्क के जवाब को देखो, जो स्पष्ट रूप से एक ही दरार कानूनी उसे की रक्षा टीम नहीं है)

---

तो तुम एक कलाकारों के मामूली भूमि के ऊपर है, लेकिन नहीं की गणना की भारी भूमि के ऊपर है।

Answer 2

इसमें IList<T> लागू करने वाली किसी भी चीज़ के लिए अनुकूलन शामिल है, इस स्थिति में यह केवल लंबाई -1 पर आइटम को देखता है।

ध्यान रखें कि सामान के विशाल बहुमत आप में भेज देंगे IList<T>

List<int> 
int[] 

और इतने पर लागू करेगा ... सभी को लागू IList<T>

जो लोग कोड में नहीं देख सकते हैं के लिए

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Diagnostics; 

namespace ConsoleApplication4 { 
    class Program { 

     static void Profile(string description, int iterations, Action func) { 

      // clean up 
      GC.Collect(); 
      GC.WaitForPendingFinalizers(); 
      GC.Collect(); 

      // warm up 
      func(); 

      var watch = Stopwatch.StartNew(); 
      for (int i = 0; i < iterations; i++) { 
       func(); 
      } 
      watch.Stop(); 
      Console.Write(description); 
      Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds); 
     } 

     static void Main(string[] args) { 
      int[] nums = Enumerable.Range(1, 1000000).ToArray(); 

      int a; 

      Profile("Raw performance", 100000,() => { a = nums[nums.Length - 1]; }); 
      Profile("With Last", 100000,() => { a = nums.Last(); }); 

      Console.ReadKey(); 
     } 


    } 
} 

आउटपुट::

0,123,516 पुष्टि करते हैं, आप इसे अवलोकन का उपयोग कर पुष्टि कर सकते हैं

 
Raw performance Time Elapsed 1 ms 
With Last Time Elapsed 31 ms 

तो यह केवल 30 गुना धीमा है और आपके पास जो भी लंबाई सूची है, उस प्रदर्शन प्रोफ़ाइल को बनाए रखता है, जो चीजों की बड़ी योजना में कुछ भी नहीं है।

Answer 3

List<T> के लिए यह ओ (1) है, लेकिन अन्य गणित के लिए यह ओ (एन) हो सकता है।

Answer 4

तुम बस चिंता :)

Enumerable.Last IList<T> को IEnumerable<T> उदाहरण खिन्न करने का प्रयास के बिना List<T> साथ अंतिम उपयोग कर सकते हैं। यदि यह संभव है, तो यह सूचकांक और गणना संपत्ति का उपयोग करता है।

यहाँ कार्यान्वयन का हिस्सा है के रूप में Reflector यह देखता है:

IList<TSource> list = source as IList<TSource>; 
if (list != null) 
{ 
    int count = list.Count; 
    if (count > 0) 
    { 
     return list[count - 1]; 
    } 
} 

Answer 5

लघु जवाब:

हे (1)।

स्पष्टीकरण:

ऐसा नहीं है कि अंतिम() के लिए सूची का उपयोग करता गणना() विस्तार विधि स्पष्ट है।

गणना() क्रम में संग्रह की चेकों के प्रकार और गणना संपत्ति का उपयोग करता है, तो यह उपलब्ध है। सूची के लिए

गणना संपत्ति हे (1) जटिलता इसलिए अंतिम() विस्तार विधि है।