python - क्यों अधिकतम की तुलना में धीमी है?




sorting max (2)

मैंने पाया है कि max पायथन 2 और 3 में sort फ़ंक्शन की तुलना में धीमा है।

अजगर २

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'        
1000 loops, best of 3: 342 usec per loop

अजगर ३

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop

sort फ़ंक्शन ( O(nlogn) ) की तुलना में max ( O(n) ) धीमा क्यों है ?


पायथन में timeit मॉड्यूल का उपयोग करते समय आपको बहुत सावधान रहना होगा।

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'

यहाँ रैंडमाइज्ड कोड एक बार रैंडमाइज्ड एरे का उत्पादन करने के लिए चलता a । फिर बाकी कोड कई बार चलाया जाता है। पहली बार यह सरणी को सॉर्ट करता है, लेकिन हर बार जब आप पहले से ही सॉर्ट किए गए सरणी पर सॉर्ट विधि को कॉल कर रहे होते हैं। केवल सबसे तेज़ समय लौटाया जाता है, इसलिए आप वास्तव में समय दे रहे हैं कि पहले से ही सॉर्ट किए गए सरणी को क्रमबद्ध करने में पाइथन को कितना समय लगता है।

पायथन के सॉर्ट एल्गोरिथ्म का हिस्सा यह पता लगाने के लिए है कि सरणी पहले से ही आंशिक रूप से या पूरी तरह से सॉर्ट की गई है। जब यह पूरी तरह से हल हो जाता है तो इसे यह पता लगाने के लिए सरणी के माध्यम से एक बार स्कैन करना पड़ता है और फिर यह बंद हो जाता है।

अगर इसके बजाय आपने कोशिश की:

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'

तब सॉर्ट हर टाइमिंग लूप पर होता है और आप देख सकते हैं कि किसी ऐरे को सॉर्ट करने का समय वास्तव में केवल अधिक से अधिक वैल्यू खोजने की तुलना में अधिक लंबा होता है।

संपादित करें: @ स्काइकिंग का answer बताता है कि मैंने जिस हिस्से को अस्पष्टीकृत छोड़ दिया था: a.sort() जानता है कि यह एक सूची पर काम कर रहा है ताकि सीधे तत्वों तक पहुंच सके। max(a) किसी भी मनमाना चलने पर काम करता है ताकि सामान्य पुनरावृत्ति का उपयोग करना पड़े।


यह इसलिए हो सकता है क्योंकि l.sort list सदस्य है जबकि max एक सामान्य कार्य है। इसका मतलब यह है कि l.sort list के आंतरिक प्रतिनिधित्व पर भरोसा कर सकता है जबकि max को सामान्य पुनरावृत्ति प्रोटोकॉल से गुजरना होगा।

यह बनाता है कि l.sort लिए प्रत्येक तत्व लाने वाले प्रत्येक तत्व की तुलना में अधिक तेज़ है जो max करता है।

मेरा मानना ​​है कि यदि आप इसके बजाय sorted(a) उपयोग करते हैं, तो आपको max(a) की तुलना में परिणाम धीमा मिलेगा।






python-internals