Linq साथ quicksort प्रदर्शन लाभ गुजर टी [] बनाम IEnumerable <T>

Question

बस मस्ती के लिए मैं Linq के साथ सी # में एक quicksort कार्यान्वयन बनाया:

public static IEnumerable<T> quicksort<T>(IEnumerable<T> input) where T : IComparable<T>{ 
    if (input.Count() <= 1) return input; 
    var pivot = input.FirstOrDefault(); 
    var lesser = quicksort(input.Skip(1).Where(i => i.CompareTo(pivot) <= 0)); 
    var greater = quicksort(input.Where(i => i.CompareTo(pivot) > 0)); 
    return lesser.Append(pivot).Concat(greater); 
} 

यह बारे में 13 सेकंड में 10000 यादृच्छिक पूर्णांकों क्रमबद्ध करता है।

लगभग 700 गुना बेहतर प्रदर्शन में सूची परिणामों के बजाय int [] का उपयोग करने के लिए इसे बदल रहा है! यह केवल 10000 यादृच्छिक पूर्णांक को क्रमबद्ध करने के लिए 21ms लेता है।

public static T[] quicksortArray<T>(T[] input) where T : IComparable<T>{ 
    if (input.Count() <= 1) return input; 
    var pivot = input.FirstOrDefault(); 
    var lesser = quicksortArray(input.Skip(1).Where(i => i.CompareTo(pivot) <= 0).ToArray()); 
    var greater = quicksortArray(input.Where(i => i.CompareTo(pivot) > 0).ToArray()); 
    return lesser.Append(pivot).Concat(greater).ToArray(); 
} 

बस कोड मैं इस मान लिया है | बदतर प्रदर्शन करना होगा पर देख रहे हैं। मैंने माना कि .ToArray() स्मृति में एक अतिरिक्त सरणी बनाएगा और वहां सभी पूर्णांक कॉपी करेगा। मुझे लगता है कि एक सूची बनाकर एक सरणी बनाम पास करना एक ही समय लेना चाहिए।

तो यह विशाल प्रदर्शन अंतर कहां से आता है?

Answer 1

यही कारण है कि आपको बहुत कई बार IEnumerable पुनरावृत्त करने के बारे में सावधान रहना चाहिए।

पहली बार जब आप quicksort पर कॉल करते हैं, तो List कहें। यह quicksort दो बार, उन मामलों में से प्रत्येक में, IEnumerable जिसे आप पास कर रहे हैं, एक क्वेरी का प्रतिनिधित्व करता है जो पहले आइटम को छोड़ देगा और फिर उसके बाद प्रत्येक आइटम पर तुलना करेगा। फिर आप उस क्वेरी को ले लें और इसे quicksort के उदाहरणों को पास करें, लेकिन क्वेरी को न केवल पहले आइटम को छोड़ दें और इसके बाद प्रत्येक आइटम की तुलना करें, लेकिन फिर उस क्वेरी के परिणामों के पहले आइटम को छोड़ दें और फिर प्रत्येक की तुलना करें के बाद आइटम कुछ के लिए। इसका अर्थ यह है कि जब तक आप अंततः एक मूल्य तक पहुंच जाते हैं, तो आपके पास एक क्वेरी है जो लॉग (एन) स्किप्स का प्रतिनिधित्व करती है, और प्रत्येक आइटम को अनुक्रम में एक मूल्य लॉग (एन) बार की तुलना कर रही है।

अपने दूसरे कार्यान्वयन आप में गुजर नहीं कर रहे हैं में quicksort को प्रश्नों, आप उनके मूल्यों को उन प्रश्नों का मूल्यांकन कर रहे हैं और आपरेशन, जो तब उन मूल्यों को दो बार उपयोग कर सकते हैं करने के लिए मूल्यों में गुजर के बजाय लगातार कई बार एक जटिल जटिल क्वेरी प्रदर्शन करते हैं।

Answer 2

linq प्रश्नों के बारे में बात वे आलसी हैं, तब तक उनका मूल्यांकन नहीं किया जाएगा जब तक कि आप ToArray या ToList जैसी विधि को कॉल न करें। उदाहरण के लिए अपने पहले कोड में, यह प्रश्न:

input.Skip(1).Where(i => i.CompareTo(pivot)) 

कम से कम दो बार हर बार जब आप FirstOrDefault के लिए quicksort फोन, Count() के लिए एक बार और एक बार मूल्यांकन किया जाएगा। जिसका मतलब है कि प्रत्येक कॉल के लिए फ़िल्टरिंग ऑपरेशन दोहराया जाएगा। जब आप दूसरी तरफ ToArray का उपयोग करते हैं, क्योंकि आपके पास पहले से ही एक सरणी में फ़िल्टर किए गए तत्व हैं, Where हर बार निष्पादित नहीं किया जाएगा, इसे ToArray पर कॉल करने के बाद इसे निष्पादित किया जाएगा और यही वह है। कोड के बीच यह अंतर है, इस पर आधारित आप अन्य भागों के लिए गणित कर सकते हैं।