linq के बिग ओ क्या है। कहाँ?

Question

मैं सूची से वस्तुओं को फ़िल्टर करने के बारे में कुछ तुलना कर रहा हूं। मैं इसे सीधे करने के लिए अनिश्चित हूं जो ओ (एन), या उपयोग कर रहे हैं। जहां()। एक साधारण डेटा सेट पर I made a simple example to test .Where()। एन = 100 आइटम हैं, और जब मैं फंक्शन BigO() में लाइन पर डीबगर चलाता हूं तो मुझे लगता है कि यह 100 गुना मुझे लगता है। जहां भी() ओ (एन) है। जो मैं समझ नहीं पाया था, जहां ऑपरेशन के दौरान डेटा संग्रहीत किया जा रहा था और मुझे यकीन नहीं था कि क्या कोई जटिलता बढ़ रही है।

क्या मुझे कुछ याद आ रहा है, या है। जहां() ओ (एन)?

public class ListerFactory 
{ 

public class Lister 
{ 
    bool includeItem { get; set; } 
} 

List<Lister> someList { get; set; } 

public ListerFactory() 
{ 
    someList = new List<Lister>(); 
    BuildLister(); 
}  

public void BuildLister() 
{ 
    for(int i = 0; i < 100; i++) 
    { 
    var inc = new Lister(); 
    inc.includeItem = i % 2; 
    someList.Add(inc); 
    } 
    BigO(); 
} 

public void BigO() 
{ 
    someList = someList.Where(thisList => thisList.includeItem == true).ToList(); 
} 
} 

Answer 1

Where() ओ (1) है; यह वास्तव में कोई काम नहीं करता है।

संग्रह के माध्यम से लूपिंग Where() द्वारा लौटा ओ (एन) है। ..

ओ (एन) जो आप देख रहे हैं ToList() का परिणाम है, जो ओ (एन) है।
यदि आप एक ओ (एन) एल्गोरिदम के लिए Where() क्वेरी पास करते हैं, तो आप कॉलबैक निष्पादन n बार देखेंगे। (मानते हैं कि एल्गोरिदम कहीं भी कैश नहीं करता है)

इसे स्थगित निष्पादन कहा जाता है।

यह सभी LINQ प्रदाताओं के बारे में अधिकतर नहीं है; यह LINQ प्रदाता के लिए सभी कॉलों को बेसब्री से निष्पादित करने के लिए समझ में नहीं आता है।

---

LINQ से ऑब्जेक्ट्स के मामले में, यह मानता है कि स्रोत संग्रह का गणक ओ (एन) है।
यदि आप कुछ अजीब संग्रह का उपयोग कर रहे हैं जो ओ (एन) से भी बदतर हो जाता है (दूसरे शब्दों में, यदि MoveNext() ओ (1) से भी बदतर है), Where() उस से घिरा होगा।

अधिक सटीक होने के लिए, Where() क्वेरी की गणना करने की समय जटिलता मूल गणना की समय जटिलता के समान ही है।

इसी तरह, मुझे लगता है कि कॉलबैक ओ (1) है।
यदि ऐसा नहीं है, तो आपको मूल गणना की जटिलता से कॉलबैक की जटिलता को गुणा करने की आवश्यकता होगी।

Answer 2

पाठ्यक्रम के संग्रह के स्रोत पर निर्भर करता है।

मैं @ एसएलएक्स से असहमत हूं कि एल्गोरिदम O(1) है क्योंकि Where() पर एक प्रश्न उस स्थिति से मेल खाने वाले उम्मीदवार की तलाश में रहेगा। उस अर्थ में यह nWhere खंड से पहले पूरे संग्रह को उत्पन्न करने के लिए काम की मात्रा के साथ सबसे खराब स्थिति O(n) होगा।

हालांकि वह एक बिंदु यह एल्गोरिथ्म है कि संग्रह (उदाहरण के लिए पैदावार पर निर्भर करता है। इसके अलावा एल्गोरिथ्म है अगर यह एक सूची है कि पहले से ही किया गया है सूची उपज का निर्माण n संग्रह में आइटम्स की संख्या के साथ O(n) है कि ऐसा लगता है कि कोई मैच आवश्यक नहीं है O(1)। यदि उपज एल्गोरिदम O(n) है और मैच एल्गोरिदम O(m) समय जटिलता O(n*m) है।उदाहरण के लिए

लें पूर्णांकों का एक संग्रह:

int[] test = new int[] {1,2,3,4,5,6,7,8,9,10,7,5,0,1,5,6}; 

यदि आप एक Where() खंड के साथ सभी पूर्णांकों जो कम से कम दो बार होते हैं आप ऐसा कर सकता है वापस जाने के लिए चाहते हैं:

test.Where(x => test.Count(y => x == y) >= 2); 

एल्गोरिदम O(n^2)

दूसरा होगा आप आलसी सेटिंग के साथ संग्रह भी बना सकते हैं:

public IEnumerable<int> GenerateCollection() { 
    //some very complex calculation, here replaced by a simple for loop 
    for(int i = 0; i < 150; i++) { 
     yield return i; 
    } 
} 

आपका एल्गोरिदम हालांकि पहले सूची उत्पन्न करता है। तो टाइमकप्लेक्सिटी O(n) है।

सूचना तथापि यदि आप के बाद पूरे संग्रह पुनरावृति जहां timecomplexity अभी भी O(n*m) और नहींO(n*n*m) है। ऐसा इसलिए है क्योंकि एक बार उम्मीदवार का मिलान हो जाने पर, इस पर पुनर्विचार नहीं किया जाएगा।