क्रमशः अधिकतम धीमा क्यों है?

Question

मैंने पाया कि max 3.

अजगर 2 में sort समारोह और की तुलना में धीमी अजगर 2

$ 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 

अजगर 3

$ 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 

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

Answer 1

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

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

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

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

यदि इसके बजाय आप की कोशिश की:

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

तो तरह हर समय पाश पर होता है और आप देख सकते हैं कि एक सरणी छँटाई के लिए समय वास्तव में बहुत लंबे समय तक की तुलना में सिर्फ अधिकतम मूल्य मिल रहा है।

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

Answer 2

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

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

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

Answer 3

सबसे पहले, ध्यान दें कि max() uses the iterator protocol, जबकि list.sort() uses ad-hoc code। जाहिर है, एक इटरेटर का उपयोग करना एक महत्वपूर्ण ओवरहेड है, यही कारण है कि आप समय में उस अंतर को देख रहे हैं।

हालांकि, इसके अलावा, आपके परीक्षण उचित नहीं हैं। आप एक ही सूची में एक ही सूची में a.sort() चला रहे हैं। algorithm used by Python विशेष रूप से पहले से ही (आंशिक रूप से) क्रमबद्ध डेटा के लिए तेज़ होने के लिए डिज़ाइन किया गया है। आपके परीक्षण कह रहे हैं कि एल्गोरिदम अच्छी तरह से अपना काम कर रहा है।

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

यहाँ मैं हर बार सूची की एक प्रति बना रहा हूं:

ये निष्पक्ष परीक्षण कर रहे हैं। जैसा कि आप देख सकते हैं, परिणामों की परिमाण का क्रम अलग है: माइक्रो-बनाम मिलीसेकंड, जैसा कि हम उम्मीद करेंगे।

और याद रखें: बड़ा-ओह ऊपरी बाउंड निर्दिष्ट करता है! पायथन के सॉर्टिंग एल्गोरिदम के लिए निचली बाउंड Ω (n है)। हे होने के नाते (n लॉग n) स्वचालित रूप से संकेत नहीं करता है कि हर रन एक समय के लिए n लॉग n आनुपातिक लेता है। यह यह भी इंगित नहीं करता है कि इसे ओ (एन) एल्गोरिदम से धीमा होना चाहिए, लेकिन यह एक और कहानी है। समझने के लिए महत्वपूर्ण है कि कुछ अनुकूल मामलों में, ओ (n लॉग n) एल्गोरिदम ओ (n) समय या उससे कम में चला सकता है।