क्यों l.insert (0, i) lyappend (i) से पाइथन में धीमी है?

Question

मैंने पायथन में एक सूची को उलट करने के दो अलग-अलग तरीकों का परीक्षण किया।

import timeit 

value = [i for i in range(100)] 
def rev1(): 
    v = [] 
    for i in value: 
     v.append(i) 
    v.reverse() 

def rev2(): 
    v = [] 
    for i in value: 
     v.insert(0, i) 

print timeit.timeit(rev1) 
print timeit.timeit(rev2) 

दिलचस्प बात यह है कि दूसरी विधि जो पहले तत्व के मान को सम्मिलित करती है वह पहले की तुलना में काफी धीमी है।

20.4851300716 
73.5116429329 

यह क्यों है? ऑपरेशन के मामले में, सिर पर एक तत्व डालना महंगा नहीं लगता है।

Answer 1

insertO(n) ऑपरेशन है क्योंकि इसमें डालने की स्थिति में या उसके बाद सभी तत्वों को स्थानांतरित करने की आवश्यकता होती है। दूसरी ओर, append, आमतौर पर O(1) (और O(n) सबसे खराब मामले में, जब अधिक स्थान आवंटित किया जाना चाहिए)। यह पर्याप्त समय अंतर बताता है।

इन तरीकों की समय जटिलताओं को पूरी तरह से here दस्तावेज किया गया है।

मैं उद्धृत:

आंतरिक, एक सूची एक सरणी के रूप में प्रस्तुत किया जाता है; सबसे बड़ी लागत वर्तमान आवंटन आकार से परे बढ़ने से आती है (क्योंकि सबकुछ आगे बढ़ना चाहिए), या शुरुआत के करीब कहीं डालने या हटाने से (क्योंकि उसके बाद सबकुछ आगे बढ़ना चाहिए)।

अब, वापस अपने कोड के लिए जा रहा है, हम देख सकते हैं कि rev1() एक O(n) कार्यान्वयन है जबकि rev2() तथ्य O(n2) में है, इसलिए यह भावना है कि rev2() बहुत धीमी हो जाएगा बनाता है।

Answer 2

पायथन में, सूचियों को सरणी के रूप में लागू किया जाता है। यदि आप किसी तत्व को सरणी में जोड़ते हैं, तो सरणी के लिए आरक्षित स्थान बस विस्तारित होता है। यदि आप एक तत्व तैयार करते हैं, तो सभी तत्व 1 से स्थानांतरित होते हैं और यह बहुत महंगा होता है।

Answer 3

आप ऑनलाइन पाइथन सूचियों के बारे में पढ़कर इसकी पुष्टि कर सकते हैं। पायथन एक सरणी के रूप में एक सूची लागू करता है, जहां सरणी का आकार वास्तव में आपकी वर्तमान सूची के आकार से आम तौर पर बड़ा होता है। अप्रयुक्त तत्व सरणी के अंत में हैं और नए तत्वों का प्रतिनिधित्व करते हैं जिन्हें सूची के अंत में जोड़ा जा सकता है, शुरुआत में नहीं। पायथन एक शास्त्रीय अमूर्त लागत दृष्टिकोण का उपयोग करता है ताकि औसतन, सूची के अंत में संलग्न होने पर आप (1) समय लेते हैं यदि आप परिशिष्ट का एक गुच्छा करते हैं, हालांकि कभी-कभी एक एकल परिशिष्ट सरणी को पूर्ण होने का कारण बनता है, इसलिए एक नया बड़ा सरणी बनाने की जरूरत है, और सभी डेटा नए सरणी में कॉपी किया गया है। दूसरी तरफ, यदि आप हमेशा सूची के सामने डालेंगे, तो अंतर्निहित सरणी में सभी तत्वों को सरणी की शुरुआत में नए तत्व के लिए जगह बनाने के लिए एक अनुक्रमणिका पर स्थानांतरित करने की आवश्यकता है। इसलिए, संक्षेप में, यदि आप एन सम्मिलन करके एक सूची बनाते हैं, तो कुल रनिंग समय ओ (एन) होगा यदि आप हमेशा सूची के अंत में नए आइटम जोड़ते हैं, और यह ओ (एन^2) होगा आप हमेशा सूची के सामने संलग्न होते हैं।