记忆化递归阶乘函数？

Question

我知道如何在Python中轻松地进行记忆化，但我需要一种更快的方法来计算它们，因此我正在使用C ++。然而，我不知道如何进行记忆化。我知道这是将值存储到数组或向量中，然后在检索时扫描其值，但如果能看到如何实现这一点，那真的很有帮助，这样我就可以尝试它的速度。

- John Smith

---

我没给你的回答点“踩”。但是我很确定答案是否定的。与递归斐波那契算法不同，对于阶乘算法来说，记忆化没有任何好处。 - Mysticial

@Mystical：我不太同意。斐波那契数列可以像计算阶乘一样用O(n)算法来写。记忆化的权衡是占用O(n)内存进行O(1)查找。对于相对较小的n，做n次乘法或加法很快。但如果你反复调用它，记忆化可以帮助。 - Mike Bailey

@MikeBantegui 斐波那契数列可以在O(pow)的时间复杂度内计算，其中pow是您的power()函数的复杂度。它有一个闭合公式。 - amit

我使用装饰器语法来完成它，所以我不确定如何翻译它。 - John Smith

这里有一个不太好写的问题，但其中蕴含着一个很好的问题。记忆化是一种技术，在某些语言中几乎可以无形地实现，而在其他语言中则需要更多的工作。我认为想知道如何以最方便和通用的方式在C++中实现它是没有问题的。 - DavidO

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

- Kerrek SB

---

r值还不错，至少对于我在你的记忆化程序上尝试的东西来说是这样。;) - CoffeDeveloper

@DarioOO：谢谢你的确认！ - Kerrek SB

Answer 2

我认为在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类的实例，该实例将我们的值类型和处理函数作为模板参数，然后只需将此类调用为函数即可。

- Charles Keepax

---

这个不起作用。第一次调用 calc() 调用了未经缓存的原始 calc，如果它是递归的，则永远不会再次查找缓存。 - Senti Bachcha

公平地说，对于重复查找，这确实有效；但是OP想要记忆化来加速递归函数。这在递归函数中非常需要，例如对于大的n的factorial(n)，或者在动态规划解决方案中。 - Senti Bachcha

Answer 3

没有学习递归的学生会使用那种方法计算阶乘。

记忆化是一个非常好的想法，特别是如果你要反复调用该方法。为什么要浪费好的工作呢？

另一个考虑因素是更好的计算阶乘的方法：使用伽玛函数的自然对数。它可以更长时间地抵抗溢出，因为您会返回一个双精度值。自然对数增长比值慢。如果您正在计算组合，则自然对数将乘除法变为加减法。

但是，无论如何，对于您使用的任何实现，请进行记忆化。如果您使用C++编写它，我建议使用以参数x为键，ln(gamma(x))为值的std:map。

很抱歉，自从我写过C++和STL已经太长时间了。我宁愿使用具有O(1)读取访问时间的哈希映射，而不是在O(n)中迭代键。

- duffymo

Answer 4

我喜欢使用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];
    });
}

- Charles Pehlivanian

---

问题在于内部调用不经过记忆化。 - Johan Lundberg

重复的、冗余的cache[t]查找真的很浪费，而且外层的cache对象是不必要的，当存在模板时，std::function也是不必要的... 抱歉 :-) - underscore_d