कार्यात्मक भाषाओं का उपयोग बार-बार गणना मूल्यों के विरुद्ध मदद करता है?

Question

पर विचार करें एक समारोह च (एक्स, वाई):

f(x,0) = x*x; 
f(0,y) = y*(y + 1); 
f(x,y) = f(x,y-1) + f(x-1,y); 

एक है कि लागू करने के लिए सी जैसे कुछ भाषा में रिकर्सिवली की कोशिश करता है ++ वह एक समस्या का सामना करेंगे।

मान लीजिए कि फ़ंक्शन को पहले x = x0 और y = y0 के साथ बुलाया जाता है। फिर किसी भी जोड़ी (x, y) के लिए जहां 0 <= x < x0 और 0 <= y < y0 इंटरमीडिएट मानों की गणना कई बार की जाएगी - रिकर्सिव कॉल एक विशाल पेड़ बन जाएगा जिसमें वास्तव में कई पत्तियों में एक ही जोड़े (x, y) होंगे। जोड़े (x, y) के लिए जहां x और y दोनों 0 मानों के करीब हैं, कई बार गणना की जाएगी।

उदाहरण के लिए, मैंने सी ++ में लागू एक समान कार्य का परीक्षण किया - x=20 और y=20 के लिए इसकी गणना में लगभग 4 घंटे लगते हैं (हाँ, चार पृथ्वी घंटे!)।

जाहिर है कि कार्यान्वयन को इस तरह से फिर से लिखा जा सकता है कि बार-बार गणना नहीं होती - या तो इसे या कैश तालिका के साथ।

सवाल यह है: क्या क्रियात्मक भाषाएं बेहतर प्रदर्शन करती हैं और उपरोक्त उपरोक्त कार्य को कार्यान्वित करते समय बार-बार गणना की जाती हैं?

Answer 1

अवधि तुम यहाँ के लिए देख रहे Memoization है:

कंप्यूटिंग में, Memoization एक अनुकूलन मुख्य रूप से इस्तेमाल कंप्यूटर प्रोग्राम तेजी लाने के लिए तकनीक फ़ंक्शन कॉल होने से परिणामों की गणना दोहराने से बचें है पूर्व-संसाधित इनपुट के लिए।

नहीं, कार्यात्मक भाषा स्वचालित रूप से ज्ञापन को लागू नहीं करती है। आप इसे इन्हें कार्यान्वित कर सकते हैं, लेकिन सी ++ में भी। हालांकि, यह सच है कि जब आप पूरी तरह से कार्यात्मक कोड लिखते हैं (यानी कोई दुष्प्रभाव नहीं), तो ज्ञापन आसान है। कुछ गतिशील भाषाओं (उदाहरण के लिए पर्ल) में ऑटो-स्मोइजेशन मॉड्यूल होते हैं जो किसी भी फ़ंक्शन को आसानी से याद कर सकते हैं। Automatic memoization section of the Wikipedia article में इस विषय की चर्चा है।

उदाहरण के लिए यहाँ एक भोली सी ++ फाइबोनैचि है:

long fib_rec(long index) 
{ 
    if (index < 2) 
     return index; 
    else 
     return fib_rec(index - 1) + fib_rec(index - 2); 
} 

और यहाँ एक memoized संस्करण है:

long fib_memoized_aux(vector<long>& cache, long index) 
{ 
    if (cache[index] >= 0) 
    return cache[index]; 

    cache[index] = fib_memoized_aux(cache, index - 1) + fib_memoized_aux(cache, index - 2); 
    return cache[index]; 
} 


long fib_memoized(long index) 
{ 
    vector<long> cache(index + 1, -1); 
    cache[0] = 0; 
    cache[1] = 1; 

    return fib_memoized_aux(cache, index); 
}