记忆,递归因子函数？

Question

我知道如何在Python中轻松进行memoization,但我需要一种更快的方式来计算它们,所以我使用的是C++.但是,我不知道如何记忆.我知道它是关于将数值存储到数组或向量中,然后在检索时扫描它的值,但是看看如何完成它真的很有帮助,所以我可以尝试它的速度.

Answer 1

只是为了好玩,这是我前段时间写的一个小型通用记忆.它需要可变参数模板,当然:

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;
}

Answer 2

那么我能想到用C++做的最好的方法可能是使用一个函数对象来存储memoized值.我想这可能与你的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;
    }
  }
};

代码定义了一个模板类,它接受一个typename和一个函数指针,然后在类上定义函数运算符,允许它被调用.函数运算符接受输入值检查所述值是否在映射中,然后简单地从映射返回它或计算它(使用函数指针),将其添加到映射然后返回它.

假设您定义了一些处理函数,例如:

int unity(int in) { return in; }

你会使用这样的代码:

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

因此,我们定义了一个mem类的实例,它将我们的值类型和处理函数作为模板参数,然后简单地将此类称为函数.