अधिकतम (पुनरावर्तनीय) बराबर लूप की तुलना में बहुत धीमा क्यों करता है?

Question

मैंने एक मामूली रिफैक्टरिंग से एक अजीब प्रदर्शन हिट देखा जो एक लूप को max पर रिकर्सिव फ़ंक्शन के अंदर कॉल के साथ बदल देता है।

यहाँ सबसे सरल प्रजनन है मैं उत्पादन कर सकता है: मानक प्रत्यावर्तन का उपयोग कर दोनों f1 और f2 calculate भाज्य

import time 

def f1(n): 
    if n <= 1: 
     return 1 
    best = 0 
    for k in (1, 2): 
     current = f1(n-k)*n 
     if current > best: 
      best = current 
    return best 

def f2(n): 
    if n <= 1: 
     return 1 
    return max(f2(n-k)*n for k in (1, 2)) 


t = time.perf_counter() 
result1 = f1(30) 
print('loop:', time.perf_counter() - t) # 0.45 sec 

t = time.perf_counter() 
result2 = f2(30) 
print('max:', time.perf_counter() - t) # 1.02 sec 

assert result1 == result2 

लेकिन में जोड़ा एक अनावश्यक अधिकतम के साथ (सिर्फ इसलिए मैं एक प्रत्यावर्तन में max उपयोग करने के लिए मिलता है, जबकि अभी भी रखने रिकर्सन सरल):

# pseudocode 
factorial(0) = 1 
factorial(1) = 1 
factorial(n) = max(factorial(n-1)*n, factorial(n-2)*n) 

यह ज्ञापन के बिना कार्यान्वित किया गया है, इसलिए कॉल की घातीय संख्या है।

max(iterable) के साथ कार्यान्वयन लूप के साथ एक से दो गुना धीमा है।

विचित्र रूप से, max बनाम लूप की सीधी तुलना प्रभाव (संपादित करें: कभी भी ध्यान न दें, @TimPeters उत्तर देखें) का प्रदर्शन नहीं किया। इसके अलावा, अगर मैं max(iterable) के बजाय max(a, b) का उपयोग करता हूं तो प्रदर्शन विसंगति गायब हो जाती है।

Answer 1

यह जनरेटर अभिव्यक्ति के कारण max फ़ंक्शन के लिए वास्तव में अनुचित है, जिसे आप इसे खिला रहे हैं। कि लपेटता;

f2 के हर मंगलाचरण एक नया बंद n के लिए बनाने की आवश्यकता है के लिए, एक नया कार्य ('The Details' of PEP 289 देखते हैं कि जिस तरह से जनरेटर का भाव, और अजगर 3 मेरा मानना ​​है कि जब से सूची का भाव, कार्यान्वित कर रहे हैं है) बनाने की ज़रूरत जेन-एक्सप का प्रतिनिधित्व करने वाले कोड ऑब्जेक्ट को ऊपर रखें। फिर यह फ़ंक्शन, जो अन्य कार्यों को स्वचालित रूप से कॉल करता है, फिर से कॉल किया जाता है।

प्रश्न में बाइट-कोड का एक छोटा सा टुकड़ा:

14 LOAD_CLOSURE    0 (n) 
16 BUILD_TUPLE    1 
18 LOAD_CONST    2 (<code object <genexpr> at 0x7f1b667e1f60, file "", line 16>) 
20 LOAD_CONST    3 ('f2.<locals>.<genexpr>') 
22 MAKE_FUNCTION   8 
24 LOAD_CONST    5 ((1, 2)) 
26 GET_ITER 
28 CALL_FUNCTION   1 

आप, ज़ाहिर है, इस तरह के किसी भी निर्देश f1 के मामले में नहीं दिख रहा है के बाद से यह सिर्फ कॉल कर रही है।

जब आप तो अपनी max समारोह, f2, समय की एक महत्वपूर्ण नंबर पर कॉल के रूप में आप कर रहे हैं जब रिकर्सिवली 30, भूमि के ऊपर सिर्फ अप बवासीर के भाज्य की गणना।

फ़ंक्शन चीज़ की एक सूची समझ संस्करण एक ही मुद्दे से काफी पीड़ित है। यह थोड़ा तेज़ है क्योंकि जनरेटर अभिव्यक्तियों की तुलना में सूची की समझ तेज है।

यदि मैं max(iterable) के बजाय max(a, b) का उपयोग करता हूं तो प्रदर्शन विसंगति गायब हो जाती है।

बिल्कुल, इस मामले में प्रत्येक कॉल के लिए कोई फ़ंक्शन नहीं बनाया गया है, इसलिए आप उस ओवरहेड ढेर को नहीं देख रहे हैं। आप बस यहां तर्क प्रदान कर रहे हैं।

Answer 2

के रूप में "एक उत्तर" क्योंकि उपयोगी स्वरूपण टिप्पणी में असंभव है इस पोस्ट करना:

$ python -m timeit "max(1, 2)" # straight 
10000000 loops, best of 3: 0.148 usec per loop 

$ python -m timeit "max([i for i in (1, 2)])" # list comp 
1000000 loops, best of 3: 0.328 usec per loop 

$ python -m timeit "max(i for i in (1, 2))" # genexp 
1000000 loops, best of 3: 0.402 usec per loop 

जो दिखाता है कि प्रत्यावर्तन एक रेड हेरिंग है। यह आम तौर पर सच है, क्योंकि ये परिणाम दिखाते हैं कि एक जीनएक्सपी एक सूचीकंप की तुलना में धीमी है, जो बदले में न तो धीमा है। चूंकि आपका कोड से अधिक अधिकतम कर रहा है, इसलिए समय अंतर भिन्न नहीं हैं - लेकिन चूंकि यह थोड़ा केवल अधिकतम से अधिक है, अधिकतम भाग की गति अभी भी बहुत महत्वपूर्ण है।