ज्ञापन, पुनरावर्ती फैक्टोरियल समारोह?

Question

मुझे पता है कि पाइथन में आसानी से ज्ञापन कैसे करें लेकिन मुझे उनकी गणना करने के लिए एक तेज़ तरीका चाहिए, इसलिए मैं सी ++ का उपयोग कर रहा हूं। हालांकि, मुझे कोई सुराग नहीं है कि कैसे याद किया जाए। मैं समझता हूं कि यह किसी सरणी या वेक्टर में मानों को संग्रहीत करने के बारे में है और फिर पुनर्प्राप्त करते समय उसके मान के लिए स्कैनिंग करने के बारे में है, लेकिन यह वास्तव में उपयोगी होगा कि यह कैसे किया जाता है ताकि मैं इसकी गति का प्रयास कर सकूं।

Answer 1

अच्छी तरह से सी ++ में ऐसा करने का सबसे अच्छा तरीका मैं ज्ञात मानों को संग्रहीत करने के लिए फ़ंक्शन ऑब्जेक्ट का उपयोग कर रहा हूं। मुझे लगता है कि यह शायद आपके अजगर सजावट के समान ही है, हालांकि मैंने कभी भी कोई पायथन नहीं किया है। कोड कुछ इस तरह दिखेगा:

template <typename T, T (*calc)(T)> 
class mem { 
    std::map<T,T> mem_map; 

public: 
    T operator()(T input) { 
    typename std::map<T,T>::iterator it; 

    it = mem_map.find(input); 
    if (it != mem_map.end()) { 
     return it->second; 
    } else { 
     T output = calc(input); 
     mem_map[input] = output; 
     return output; 
    } 
    } 
}; 

कोड एक टेम्पलेट वर्ग है कि एक typename और एक समारोह सूचक में लेता है परिभाषित करता है, समारोह ऑपरेटर तो वर्ग की इजाजत दी यह कहा जाने पर परिभाषित किया गया है। फ़ंक्शन ऑपरेटर इनपुट मान चेक में लेता है यदि कहा गया मान किसी मानचित्र में है, तो या तो इसे मानचित्र से वापस कर देता है या इसकी गणना करता है (फ़ंक्शन पॉइंटर का उपयोग करके), इसे मानचित्र में जोड़ता है और फिर उसे वापस कर देता है।

तो आप की तरह कहते हैं कुछ संसाधन समारोह को परिभाषित संभालने:

int unity(int in) { return in; } 

आप इस तरह कोड का प्रयोग करेंगे:

mem<int, unity> mem_unity; 
int y; 
y = mem_unity(10); 

तो हम मेम वर्ग है जो हमारे मान प्रकार लेता है की एक आवृत्ति को परिभाषित और टेम्पलेट पैरामीटर के रूप में प्रसंस्करण कार्य, फिर बस इस वर्ग को एक समारोह के रूप में कॉल करें।

Answer 2

छात्र सीखने के रिकॉर्जन को छोड़कर कोई भी इस तरह फैक्टोरियल की गणना नहीं करेगा।

ज्ञापन एक बहुत अच्छा विचार है, खासकर यदि आप बार-बार विधि को कॉल करने जा रहे हैं। अच्छा काम क्यों फेंक दो?

फैक्ट्रोरियल की गणना करने का एक और तरीका है: गामा फ़ंक्शन के प्राकृतिक लॉग का उपयोग करें। यह अधिक प्रवाह के खिलाफ लंबे समय तक पकड़ जाएगा, क्योंकि आप एक डबल मान वापस करते हैं। प्राकृतिक लॉग मूल्य से अधिक धीरे-धीरे बढ़ेगा। यदि आप संयोजनों की गणना कर रहे हैं, तो प्राकृतिक लॉग गुणा और विभाजन को जोड़ और घटाव में बदल देता है।

लेकिन, हर तरह से, आपके द्वारा उपयोग किए जाने वाले किसी भी कार्यान्वयन के लिए याद रखें। यदि आप इसे C++ में लिख रहे हैं, तो मैं std:map का उपयोग x के साथ तर्क के रूप में ln(gamma(x)) के साथ std:map का उपयोग करने की अनुशंसा करता हूं।

क्षमा करें, यह बहुत लंबा रहा है क्योंकि मैंने सी ++ और एसटीएल लिखा है। मैं O(1)O(n) में चाबियों को फिर से चलाने के लिए एक्सेस समय पढ़ने के साथ एक हैश मानचित्र का उपयोग करना चाहता हूं।

Answer 3

बस मस्ती के लिए, यहां कुछ समय पहले लिखा गया एक छोटा सा सामान्य ज्ञापन है। यह variadic टेम्पलेट्स की आवश्यकता है, स्वाभाविक रूप से:

template <template <typename...> class Container, typename...> struct Memo; 

template <typename R, typename... Args, template <typename...> class Container> 
struct Memo<Container, R, std::tuple<Args...>> 
{ 
    Memo(std::function<R(Args...)> f) : func(f) { } 

    R operator()(Args && ...args) 
    { 
    const auto arg = std::make_tuple(args...); 
    typename CacheContainer::const_iterator it = cache.find(arg); 

    if (it == cache.cend()) 
    { 
     it = cache.insert(typename CacheContainer::value_type(arg, func(std::forward<Args>(args)...))).first; 
     std::cout << "New call, memoizing..." << std::endl; 
    } 
    else 
    { 
     std::cout << "Found it in the cache!" << std::endl; 
    } 

    return it->second; 
    } 

private: 

    typedef Container<typename std::tuple<Args...>, R> CacheContainer; 

    std::function<R(Args...)> func; 
    CacheContainer cache; 
}; 


template <typename R, typename... Args> 
Memo<std::map, R, std::tuple<Args...>> OMapMemoize(R(&f)(Args...)) 
{ 
    return Memo<std::map, R, std::tuple<Args...>>(f); 
} 
template <typename R, typename... Args> 
Memo<std::unordered_map, R, std::tuple<Args...>> UMapMemoize(R(&f)(Args...)) 
{ 
    return Memo<std::unordered_map, R, std::tuple<Args...>>(f); 
} 

मैं, पूरी तरह से यकीन है कि अगर मैं rvalue-forwardiness अधिकार मिल गया नहीं कर रहा हूँ यह एक लंबे समय पहले कि मैं यह लिखा है के रूप में। वैसे भी, यहाँ एक परीक्षण का मामला है:

int foo(double, char) { return 5; } 

int main() 
{ 
    auto f = OMapMemoize(foo); 
    auto g = UMapMemoize(foo); 

    int a, b; 

    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 
    a = f(1.0, 'a'); 

    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 
    b = g(1.0, 'a'); 

    return a; 
} 

Answer 4

मैं के रूप में लैम्ब्डा कब्जा पर भरोसा पसंद (std=c++14 का उपयोग करता है)

template<typename R, typename... Args> 
auto memoize(std::function<R(Args...)>&& f) 
{ 
    using F = std::function<R(Args...)>; 
    std::map<std::tuple<Args...>,R> cache; 
    return ([cache = std::map<std::tuple<Args...>,R>{}, 
      f = std::forward<F>(f)](Args&&... args) mutable 
    { 
     std::tuple<Args...> t(args...); 
     if (cache.find(t) == cache.end()) 
     { 
      R r = f(std::forward<Args...>(args)...); 
      cache[t] = r; 
     } 
     return cache[t]; 
    }); 
}