我知道如何在Python中轻松地进行记忆化,但我需要一种更快的方法来计算它们,因此我正在使用C ++。然而,我不知道如何进行记忆化。我知道这是将值存储到数组或向量中,然后在检索时扫描其值,但如果能看到如何实现这一点,那真的很有帮助,这样我就可以尝试它的速度。
仅仅为了好玩,这是我一段时间前写的一个小型的通用记忆库。它自然需要可变参数模板:
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);
}
我不太确定我是否完全理解了右值引用,因为我写这段代码已经很久了。无论如何,这里是一个测试案例:
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;
}
我认为在C++中最简单的方法是使用函数对象来存储记忆化的值。我猜这可能与您的Python装饰器略有相似,尽管我从未真正做过任何Python。代码应该类似于:
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;
}
}
};
int unity(int in) { return in; }
您将像这样使用代码:
mem<int, unity> mem_unity;
int y;
y = mem_unity(10);
因此,我们定义了一个mem类的实例,该实例将我们的值类型和处理函数作为模板参数,然后只需将此类调用为函数即可。
calc()
调用了未经缓存的原始 calc
,如果它是递归的,则永远不会再次查找缓存。 - Senti Bachchafactorial(n)
,或者在动态规划解决方案中。 - Senti Bachcha我喜欢使用lambda捕获,例如(使用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];
});
}
cache[t]
查找真的很浪费,而且外层的cache
对象是不必要的,当存在模板时,std::function
也是不必要的... 抱歉 :-) - underscore_d
O(n)
算法来写。记忆化的权衡是占用O(n)
内存进行O(1)
查找。对于相对较小的n,做n次乘法或加法很快。但如果你反复调用它,记忆化可以帮助。 - Mike BaileyO(pow)
的时间复杂度内计算,其中pow
是您的power()
函数的复杂度。它有一个闭合公式。 - amit