Memoized，递归阶乘函数？ [英] Memoized, recursive factorial function?

问题描述

我知道该怎么做记忆化在Python很容易，但我需要一个更快的方法来计算他们，所以我使用C ++。不过，我不知道如何memoize的。据我所知，这是关于存储的值到一个数组或向量，然后检索扫描时，它的价值，但它会是真正有用的，看看如何做到这一点，所以我可以试试它的速度。

I know how to do memoization in Python easily but I need a faster way to compute them, so I am using C++. However, I have no clue how to memoize. I understand that it's about storing values into an array or vector and then scanning for its value when retrieving, but it'd be really helpful to see how this is done so I can try its speed.

推荐答案

嗯，我能想到的做到这一点在C ++中最巧妙的方法可能是用一个函数对象来存储memoized值。我想这可能是略有相似，你的Python的装饰，但我从来没有真正做过任何蟒蛇。在code会是这个样子：

Well the neatest way I can think of to do this in C++ is probably using a function object to store the memoized values. I guess this is probably slightly similar to your python decorator, although I have never really done any python. The code would look something like this:

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

在code定义的模板类，它在类型名称和一个函数指针，该函数运算符，然后在类允许它被称为定义。的函数运算符采用在输入值检查如果所述值是在一个地图上，然后或者简单地从地图返回它或它计算（使用函数指针），将其添加到地图，然后返回它

The code defines a template class that takes in a typename and a function pointer, the function operator is then defined on the class allowing it to be called. The function operator takes in an input value checks if said value is in a map, then either simply returns it from the map or calculates it (using the function pointer), adds it to the map and then returns it.

因此​​，假如你定义一些处理功能就好说了：

So assuming you define some processing function like say:

int unity(int in) { return in; }

您将使用code是这样的：

You would use the code like this:

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

所以，我们定义了纪念品类，它需要我们的价值类型和处理功能作为模板参数的一个实例，然后简单地调用这个类的函数。

So we define an instance of the mem class which takes our value type and processing function as template parameters, then simply call this class as a function.

这篇关于Memoized，递归阶乘函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！