支持遞歸功能的自動記憶功能

博客文章Automatic Memoization in c++0x提供了生成現有功能的記憶版本的功能。博客文章和相關代碼之前已經在stackoverflow（例如What does this C++11 code do?）中討論過，但是，這些解決方案都不能提供能夠正確記憶遞歸函數的完全通用記憶器。支持遞歸功能的自動記憶功能

當然，也有改變，通過使用像這樣的遞歸調用的伎倆（假設我們有一個memoizer比如在博客中提出的一個已經在地方叫memoize）：

std::function<int (int)> f; 
int fib(int n) { 
    if (n < 2) return n; 
    return f(n-1) + f(n-2); 
} 

int main(void) { 
    f = memoize(std::function<int (int)>(fib)); 
}

但這種感覺更像是一種解決方法，而不是一個合適的解決方案，因爲我們仍然需要訪問我們想要記憶的功能。一個合適的解決方案應該能夠完全記憶任何功能，包括某些庫中定義的功能。然而，生產這樣的解決方案似乎超出了我的範圍（假設它是可能的），因此我在問：

是否可以實現真正的通用記憶功能？
如何可以實現這樣的壯舉？

如果這是不可能的，是否至少有一種方法來推廣上述方法。沿（不編譯和無效C++）線的東西：

int fib(int n){ 
    if (n < 2) return n; 
    return this_func(n-1) + this_func(n-2); 
}

哪裏this_func是一些東西，類似於this指針一類的，但對於一個功能。 [編輯：這可能仍然從問題的困擾，該this_func指針將指向fib代替memoized fib]

來源

2014-01-10 elemakil

我不認爲今天有什麼辦法做到這一點，特別是預編譯的庫。我的第一個猜測是，在事實之後添加記憶的方法是使用鏈接器用memoized_fib（）包裝函數替換fib（）的重定位。然而，我不知道編譯和鏈接階段的細節，以瞭解內部遞歸在鏈接階段是否可用於替換。哦，我不知道有一個鏈接器可以做這種替換。 – Speed8ump

如果您希望遞歸調用使用相同的緩存，我認爲您需要以某種方式在它們之間共享緩存。也就是說，要麼使用'static'（更好，但更慢：'thread_local'）緩存或將緩存作爲附加參數傳遞。無論哪種方式都需要修改'fib'。（[wikipedia]上的一個例子]（https://en.wikipedia.org/wiki/Fixed_point_combinator#Explanation_for_imperative_programmers），它使用後一種技術，通過函數的memoized版本將緩存作爲參數傳遞。） – dyp

我的猜測是，這是不可能的，而定義的行爲的範圍內停留，因爲有無法抽象出遞歸調用。事實上，我想不出比你提供的全局變量版本更好的東西。

一個明顯的理念提供了一個抽象點更強大的比一個全局變量將是添加的功能改乘作爲第一個參數：

int fib(std::function<int (int)> rec, int n) 
{ 
    if (n < 2) return n; 
    return rec(n - 1) + rec(n - 2); 
}

然後，你可以修改你的memoize的函數傳遞memoized版本到第一個參數，並且事情應該是正常的。這個技巧通常用於完成（統一/非類型化）功能語言（如方案）中的相同目標。

但是，這種技巧依賴於一種叫做"Y combinator"的東西，我認爲它不能在C++中存在，因爲它具有無限類型。

來源

2014-01-10 15:06:11 rmcclellan

現在，'' rec'和'fib'不共享相同的簽名... – Jarod42

你是對的，我的答案是，它不起作用，因爲沒有超越標準就無法打字，因爲C++有不支持遞歸類型 – rmcclellan

以下可能會有所幫助，但它仍然是一個黑客，這是醜陋的...：

int fib(void* f, int n) 
{ 
    if (n < 2) return n; 
    auto this_func = *reinterpret_cast<std::function<int (void*, int)>*>(f); 
    return this_func(f, n - 1) + this_func(f, n - 2); 
} 


int main(int argc, char *argv[]) 
{ 
    std::function<int (void*, int n)> fib1 = &fib; 
    std::cout << fib1(reinterpret_cast<void*>(&fib1), 5) << std::endl; 

    auto f = memoize(fib1); 
    std::cout << f(reinterpret_cast<void*>(&f), 5) << std::endl; 

    return 0; 
}

我用void*因爲正確的簽名是遞歸的： -/

來源

2014-01-10 15:21:32 Jarod42

'void *'在C中也是一個問題，其中使用了包含函數指針作爲成員的IIRC'struct'。像'struct recursive_fun {using f = int（recursive_fun，int）; f * m; };'（當然你可以在C++中添加'operator（）'） – dyp

實際上，它可以通過使用緩存作爲數據成員的函數對象來簡化;） – dyp

由於高速緩存需求要通過函數調用進行共享，您必須將其作爲參數傳遞，否則將共享它。分享它的方法是使用一個函數對象：

struct fib 
{ 
    std::map<std::tuple<int>, int> cache; 

    int operator()(int n) 
    { 
     if(n < 2) return n; 

     auto memoize = [this](int p) 
     { 
      auto i = cache.find(p); 
      if(i == cache.end()) i = cache.insert({p, (*this)(p)}).first; 
      return i->second; 
     }; 

     return memoize(n-1) + memoize(n-2); 
    } 
};

在這裏你可以分解出memoize部分。

還有一個把臨時生命期作爲參數傳遞給memoized函數的技巧;是這樣的：

struct recurse // possibly a class template 
{ 
    std::function<int(int, recurse const&)> f; // possibly `mutable` 

    template<class T> 
    recurse(T&& p) : f(memoize(decltype(f){p})) 
    {} 

    int operator()(int x) const 
    { 
     return f(x, *this); 
    } 
}; 

int fib(int n, recurse const& f); 

int fib(int n, recurse const& f = {fib}) 
{ 
    if(n < 2) return n; 
    return f(n-1) + f(n-2); // or `fib(n-1, f) + fib(n-2, f)` 
}

然而，這需要memoize的變化，因爲recurse const&不能夠（應該）是內部map的一部分。

_{N.B.那些const&也可能是&&延長壽命，但是，這可能是由於移動語義造成的混淆}

來源

2014-01-10 16:37:33 dyp

支持遞歸功能的自動記憶功能

回答

相關問題