मेरे पास है;एक साधारण linq (वस्तुओं के लिए) क्वेरी की स्पेस जटिलता
var maxVal = l.TakeWhile(x=>x < val).Where(x=>Matches(x)).Max();
इसकी कितनी जगह चाहिए? क्या linq उपरोक्त की एक सूची बनाता है जहां() स्थिति, या मैक्स() मैक्स() है जो वर्तमान मैक्स() के ट्रैक को ध्यान में रखते हुए आईनेमरेबल के माध्यम से फिर से चल रहा है?
और जहां मैं इस बारे में अधिक जानकारी पा सकते हैं, इतने पर पूछ च
मैं परावर्तक कि Enumerable.TakeWhile, Enumerable.Where और Enumerable.Max में से प्रत्येक के निरंतर अंतरिक्ष में चलाने के साथ सत्यापित किया है के अलावा। नतीजतन, यह पूरी क्वेरी निरंतर अंतरिक्ष में चलनी चाहिए। TakeWhile पर विचार करने और स्थगित निष्पादन + स्ट्रीमिंग का उपयोग करने के लिए कहां अनुमान लगाया गया है, आश्चर्य की बात नहीं है। मैक्स स्थगित निष्पादन का उपयोग नहीं करता है, लेकिन केवल 'अधिकतम अब तक' और स्रोत पर गणना करने वाले को गणना करने की आवश्यकता है।
ReflectorMax() विधि के अनुसार गणना करने योग्य के माध्यम से पुनरावृत्त करता है।
और जहां मैं इस बारे में अधिक जानकारी पा सकते हैं, च
इतने पर पूछ के अलावा आप Reflector उपयोग कर सकते हैं किसी भी नेट विधानसभा के कार्यान्वयन को देखने के लिए।
Reflector आपका मित्र है।
विशेष रूप से, आप में Enumerable कक्षा में ऑब्जेक्ट्स एक्सटेंशन विधियों के लिए लिंक पर एक नज़र डाल सकते हैं।
उपरोक्त पुनरावृत्तियों का उपयोग कर रहे हैं, इसलिए वे जो भी स्थान एन्युमरेटर्स लेते हैं - आमतौर पर ओ (1) का उपयोग करते हैं। अधिकतम() ओ (1) अंतरिक्ष है।
हालांकि, ध्यान रखें कि कुछ भी डेवलपर को एक गणक लिखने से रोकता है जो स्थिर स्थान से अधिक लेता है। जैसे एक पेड़ को घुमाने के लिए ओ (लॉग एन) स्पेस की आवश्यकता हो सकती है। यह मामला है उदा। SortedDictionary<K,V> और SortedSet<K,V> के लिए।
तो यह आंशिक रूप से इस बात पर निर्भर करता है कि l आपके कोड में है।
समेकित द्वारा प्रदान की जाने वाली एकमात्र चीज जो मैंने पाया है, निरंतर कारणों में नहीं चलता है, स्पष्ट कारणों से ToList() है।
कुछ गणनाओं के साथ, यह अक्षम है, जिसमें आपके पास पहले से ही एक स्थिरता जटिलता है (आमतौर पर ओ (एन) जैसा कि आप आइटम संग्रहित कर रहे हैं) और प्रश्न में संग्रह कम समय की जटिलता के साथ एक तंत्र प्रदान करता है। यदि आप स्वयं को ऐसा संग्रह बना रहे हैं तो यह समेकित द्वारा प्रदान किए गए एक्सटेंशन के अपने संस्करणों की पेशकश करना समझ में आता है। उदाहरण के लिए, यदि आपके पास एक संग्रह है जो स्वाभाविक रूप से सॉर्ट किया गया है तो आपको ओ (एन) जटिलता (चाहे वह ओ (1), ओ (एलएन) या कुछ और होगा, से बेहतर में न्यूनतम() और अधिकतम() प्रदान करने में सक्षम होना चाहिए उस सॉर्टिंग को किस तरह रखा गया था इस पर निर्भर करता है)। चूंकि इंस्टेंस विधियां विस्तार विधियों को ओवरराइड करती हैं (जब आवृत्ति प्रकार की बजाय ऑब्जेक्ट प्रकार की अभिव्यक्ति पर कॉल किया जाता है) तो आपके ऑब्जेक्ट का उपयोग करके कोडर में कोई फर्क नहीं पड़ता है, तो आप बेहतर दक्षता प्रदान करेंगे।
मेरी जानकारी के लिए, toArray में से कोई भी(), ToList(), ToDictionary(), ToLookup(), OrderBy(), OrderByDescending(), GroupBy(), अलग() निरंतर अंतरिक्ष में रन। और भी हो सकता है। आप दक्षता बिट हालांकि के बारे में सही कर रहे हैं; मैं SortedList.Values.Max() को कॉल नहीं करूंगा, हालांकि भविष्य में एमएस किस अनुकूलन को रखेगा, जानता है। – Ani
गाह! हां, जो आप उल्लेख करते हैं वे निरंतर स्थान से ऊपर हैं, टिप्पणी करते समय वे मेरे दिमाग को फिसल देंगे। एक अनुकूलन पहले से ही में डाल दिया है कि गणना() क्या गणन एक ICollection है के लिए एक जाँच करता है और अगर ऐसा है, इसकी गणना संपत्ति का मान देता है। –
यह समझ में आता है कि मैक्स स्थगित निष्पादन का उपयोग नहीं करता है, क्योंकि यह टी को एक आईएनयूमेरेबल नहीं देता है। इसे देखने का एक अलग तरीका यह है कि उनमें से कोई वास्तव में स्थगित निष्पादन नहीं करता है; वे सभी तुरंत एक वस्तु वापस कर देते हैं जो विभिन्न तरीकों से व्यवहार करेगा जब गणना की जाएगी।मैक्स() के परिणाम हालांकि, के माध्यम से गणना नहीं है। हालांकि यह ज्यादातर चीजों के बारे में सोचने का सबसे अच्छा तरीका नहीं है, यह याद रखने की कोशिश करते समय यह मदद कर सकता है कि क्या है और स्थगित नहीं है। –