我该如何编写通用的记忆化函数？

# 将函数进行记忆化

```lua
function memoize (f)
   local cache = {}
   return function (x)
             if cache[x] then
                return cache[x]
             else
                local y = f(x)
                cache[x] = y
                return y
             end
          end
end

现在可以用memoize将任意函数换成一个记忆函数。例如，下面的代码将triangle函数替换为一个记忆函数：

triangle = memoize(triangle);

请注意要想避免栈溢出，triangle仍然需要进行种子设置。 ```

下面是一个通用的 C# 3.0 实现，如果有帮助的话：

public static class Memoization
{
    public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
    {
        var cache = new Dictionary<T, TResult>();
        var nullCache = default(TResult);
        var isNullCacheSet = false;
        return  parameter =>
                {
                    TResult value;

                    // 如果参数为 null，则返回缓存结果
                    if (parameter == null && isNullCacheSet)
                    {
                        return nullCache;
                    }

                    // 如果参数为 null，则计算结果并设置缓存
                    if (parameter == null)
                    {
                        nullCache = function(parameter);
                        isNullCacheSet = true;
                        return nullCache;
                    }

                    // 如果参数不为 null，则返回缓存结果
                    if (cache.TryGetValue(parameter, out value))
                    {
                        return value;
                    }

                    // 如果参数不为 null，则计算结果并设置缓存
                    value = function(parameter);
                    cache.Add(parameter, value);
                    return value;
                };
    }
}

(引用自一篇法语博客文章)

在 Scala 中（未经测试）：

def memoize[A, B](f: (A)=>B) = {
  var cache = Map[A, B]()

  { x: A =>
    if (cache contains x) cache(x) else {
      val back = f(x)
      cache += (x -> back)

      back
    }
  }
}

请注意，这仅适用于具有 1 阶数的函数，但是通过柯里化，您可以使其正常工作。更微妙的问题是对于任何函数 f，memoize(f) != memoize(f)。修复这个非常狡猾的方法之一是像下面这样做：

val correctMem = memoize(memoize _)

我认为这不会编译，但它确实说明了这个想法。

你对于原始问题的提问方式也不太对 ;)

下面是更好的方法:

triangle(n) = n * (n - 1) / 2

此外，假设公式没有那么优秀的解决方案，记忆化仍然是在这种情况下较差的方法。在这种情况下，最好只需编写一个简单的循环。有关更全面的讨论，请参见 此答案。

更新：评论员指出记忆化是优化递归的好方法。坦白说，在我通常使用的语言（C#）中，一般化的记忆化并不是很容易构建，因此我之前并没有考虑过这一点。在阅读下文时请将这一点牢记在心。

我认为 Luke 可能有最合适的解决方案 来解决这个问题，但记忆化通常不是解决任何栈溢出问题的通用方法。

栈溢出通常是由递归深度超出平台能够处理的范围所引起的。有时，语言支持“尾递归” ，它重复使用当前调用的上下文，而不是为递归调用创建新的上下文 。但是，很多主流的语言/平台都不支持这一点。例如，C# 没有内置对尾递归的支持。 .NET JIT 编译器的 64 位版本可以在 IL 级别应用尾递归作为优化，但如果需要支持 32 位平台，则几乎没有用处。

如果您的语言不支持尾递归，则避免栈溢出的最佳选择是将其转换为显式循环（远不如优雅，但有时是必要的），或者找到像 Luke 为这个问题所提供的非迭代算法。

拓展这个想法，也可以使用两个输入参数来记忆化函数：

function memoize2 (f)
   local cache = {}
   return function (x, y)
             if cache[x..','..y] then
                return cache[x..','..y]
             else
                local z = f(x,y)
                cache[x..','..y] = z
                return z
             end
          end
end

注意，在缓存算法中参数的顺序很重要，因此，如果函数的参数顺序在记忆化时并不重要，通过在检查缓存之前对参数进行排序，可以增加获取缓存命中的几率。

但是，需要注意的是，有些函数不能有效地进行记忆化。我编写了 memoize2 函数，以查看用于查找最大公约数的递归 欧几里得算法 是否可以加速。

function gcd (a, b)
   if b == 0 then return a end
   return gcd(b, a%b)
end

事实证明，gcd 不适用于记忆化。它执行的计算远不及缓存算法的开销。即使对于大数，它也会很快终止。一段时间后，缓存变得非常大。这个算法可能已经达到了最快的速度。

我打赌，在Lua中可以使用可变参数列表实现类似这样的功能：

local function varg_tostring(...)
    local s = select(1, ...)
    for n = 2, select('#', ...) do
        s = s..","..select(n,...)
    end
    return s
end

local function memoize(f)
    local cache = {}
    return function (...)
        local al = varg_tostring(...)
        if cache[al] then
            return cache[al]
        else
            local y = f(...)
            cache[al] = y
            return y
        end
    end
end

你也可以使用 __tostring() 元表做一些巧妙的处理，这样参数列表就可以通过 tostring() 转换了。哦，这一切都是可能的。

在不同编程语言中发布记忆化的实现

为了发布不同编程语言实现的记忆化方法，我想回复 @onebyone.livejournal.com，提供一个不改变编程语言的 C++ 示例。

首先，是单个参数函数的 memoizer：

template <class Result, class Arg, class ResultStore = std::map<Arg, Result> >
class memoizer1{
public:
    template <class F>
    const Result& operator()(F f, const Arg& a){
        typename ResultStore::const_iterator it = memo_.find(a);
        if(it == memo_.end()) {
            it = memo_.insert(make_pair(a, f(a))).first;
        }
        return it->second;
    }
private:
    ResultStore memo_;
};

只需创建一个 memoizer 实例，将函数和参数传递进去即可。只需要确保不要在两个不同的函数之间共享同一个 memo（但您可以在同一函数的不同实现之间共享它）。

接下来，是一个驱动函数和它的实现。只有驱动函数需要是公共的。

int fib(int); // driver
int fib\_(int); // implementation

实现：

int fib_(int n){
    ++total_ops;
    if(n == 0 || n == 1)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

以及用于记忆化的驱动函数：

int fib(int n) {
    static memoizer1<int,int> memo;
    return memo(fib_, n);
}

在 codepad.org 上展示输出的永久链接。通过测量调用次数来验证正确性。 （在此处插入单元测试……）

这仅针对单个输入函数进行了记忆化。有关多个参数或不同参数的通用化方法，留给读者自行探索。

Mathematica 有一种特别巧妙的记忆化方法，它依赖于哈希和函数调用使用相同的语法：

triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]

就是这样。这是因为模式匹配函数调用的规则总是先使用更具体的定义，然后再使用更一般的定义。

当然，正如人们指出的那样，这个例子有一个封闭形式的解： triangle[x_] := x*(x+1)/2。斐波那契数列是给出记忆化实现相对于非记忆化版本能够大幅加速的经典例子：

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

尽管它也有一个更为复杂的封闭形式等价物：http://mathworld.wolfram.com/FibonacciNumber.html

我不同意那个建议这种方法不适用记忆化的人，因为你可以“只需使用循环”。记忆化的重点是，任何重复的函数调用都是 O（1）时间。这比 O(n) 好得多。实际上，你甚至可以发明一种场景，其中记忆化实现比封闭形式实现具有更好的性能！

在 Perl 中，通用的记忆化很容易实现。Memoize 模块是 perl 核心的一部分，具有高可靠性、灵活性和易用性。

以下是该模块手册中的示例：

# 这是 Memoize 1.01 的文档
use Memoize；
memoize('slow_function');
slow_function(arguments);    # 比以前更快了

您可以在运行时添加、删除和自定义函数的记忆化！您可以为自定义记忆计算提供回调函数。

Memoize.pm 甚至具有使记忆缓存持久化的功能，因此无需在每次调用程序时重新填充！

这是文档链接：http://perldoc.perl.org/5.8.8/Memoize.html

以下是不将参数转换为字符串即可正常运行的代码。唯一的限制是它不能处理空参数。但是，接受的解决方案不能区分值nil和字符串"nil"，所以这可能是可以接受的。

local function m(f)
  local t = { }
  local function mf(x, ...) -- 内存函数
    assert(x ~= nil, '空参数传递给内存函数')
    if select('#', ...) > 0 then
      t[x] = t[x] or m(function(...) return f(x, ...) end)
      return t[x](...)
    else
      t[x] = t[x] or f(x)
      assert(t[x] ~= nil, '内存函数返回空值')
      return t[x]
    end
  end
  return mf
end

我受到这个问题的启发，在 Lua 中实现（另一个）灵活的记忆化函数。

https://github.com/kikito/memoize.lua

主要优点：

• 接受可变数量的参数
• 不使用 tostring；相反，它使用参数来遍历以树结构组织的缓存。
• 与返回多个返回值的函数完全兼容。

将代码粘贴在此处供参考：

local globalCache = {}

local function getFromCache(cache, args)
  local node = cache
  for i=1, #args do
    if not node.children then return {} end
    node = node.children[args[i]]
    if not node then return {} end
  end
  return node.results
end

local function insertInCache(cache, args, results)
  local arg
  local node = cache
  for i=1, #args do
    arg = args[i]
    node.children = node.children or {}
    node.children[arg] = node.children[arg] or {}
    node = node.children[arg]
  end
  node.results = results
end

-- public function

local function memoize(f)
  globalCache[f] = { results = {} }
  return function (...)
    local results = getFromCache( globalCache[f], {...} )

    if #results == 0 then
      results = { f(...) }
      insertInCache(globalCache[f], {...}, results)
    end

    return unpack(results)
  end
end

return memoize

在 C# 3.0 中，对于递归函数，可以使用以下代码：

public static class Helpers
{
    public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>,  R> f)
    {
        var map = new Dictionary<A, R>();
        Func<A, R> self = null;
        self = (a) =>
        {
            R value;
            if (map.TryGetValue(a, out value))
                return value;
            value = f(a, self);
            map.Add(a, value);
            return value;
        };
        return self;
    }
}

然后可以像这样创建一个记忆化 Fibonacci 函数：

var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));

递归不是必要的。第n个三角形数是n(n-1)/2，因此...

public int triangle(final int n){
   return n * (n - 1) / 2;
}

请不要递归这个函数。可以使用 x*(x+1)/2 公式，或者简单地遍历数值并在进行时进行备忘录操作。

int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
  sum+=i;
  memo[i] = sum;
}
return memo[n];