我正在写一个函数来查找三角数，写它的自然方法是递归的：

function triangle (x)
   if x == 0 then return 0 end
   return x+triangle(x-1)
end

但是尝试计算第一个100,000个三角形数会失败，并在一段时间后出现堆栈溢出。这是一个理想的记忆功能，但是我想要一个能够记忆传递给我的任何功能的解决方案。

解决方案

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

triangle = memoize(triangle);

请注意，为避免堆栈溢出，仍将需要播种三角形。

如果可以帮助的话，这是一个通用的C3.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;

                    if (parameter == null && isNullCacheSet)
                    {
                        return nullCache;
                    }

                    if (parameter == null)
                    {
                        nullCache = function(parameter);
                        isNullCacheSet = true;
                        return nullCache;
                    }

                    if (cache.TryGetValue(parameter, out value))
                    {
                        return value;
                    }

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

请注意，这仅适用于arity 1的功能，但是通过进行反复操作，我们可以使其生效。更微妙的问题是任何函数" f"的memoize(f)！= memoize(f)。解决此问题的一种非常偷偷摸摸的方法如下所示：

val correctMem = memoize(memoize _)

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

我们还为原始问题提出了错误的问题;)

对于这种情况，这是一种更好的方法：

三角形(n)= n *(n 1)/ 2

此外，假设公式没有这么整洁的解决方案，那么在这里进行记忆仍然是一个糟糕的方法。在这种情况下，最好只编写一个简单的循环。请参阅此答案以进行更全面的讨论。

更新：评论者指出，记忆是优化递归的好方法。诚然，我以前没有考虑过这一点，因为我通常使用的语言(C＃)工作时，通用记忆并不那么容易构建。考虑一下下面的贴子。

我认为Luke可能对这个问题有最合适的解决方案，但是备忘录通常不是解决任何堆栈溢出问题的解决方案。

堆栈溢出通常是由于递归的深度超出了平台可以处理的范围。语言有时支持"尾递归"，它重用当前调用的上下文，而不是为递归调用创建新的上下文。但是许多主流语言/平台不支持此功能。例如，没有尾递归的固有支持。 .NET JITter的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()转换参数列表。哦，可能性。

按照用不同语言发布备忘录的方式，我想用一个不改变语言的C ++示例来响应@ onebyone.livejournal.com。

首先，一个用于单个arg函数的备忘录：

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

只需创建备忘录的一个实例，并为其提供函数和参数即可。只要确保不在两个不同功能之间共享同一备忘录即可(但是我们可以在同一功能的不同实现之间共享该备忘录)。

接下来，一个驱动程序功能，以及一个实现。仅驱动程序功能需要公开
int fib(int); // 司机
int fib_(int); // 执行

实施的：

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核心的一部分，并且高度可靠，灵活且易于使用。

联机帮助页中的示例：

# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments);    # Is faster than it was before

我们可以在运行时添加，删除和自定义功能的记忆！我们可以提供用于自定义memento计算的回调。

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

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

有关最多4个参数的通用Scala解决方案，请参见此博客文章。

这是一种无需将参数转换为字符串的方法。
唯一的警告是它不能处理nil参数。但是，公认的解决方案无法将值" nil"与字符串" nil"区别开来，因此可能没问题。

local function m(f)
  local t = { }
  local function mf(x, ...) -- memoized f
    assert(x ~= nil, 'nil passed to memoized function')
    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, 'memoized function returns nil')
      return t[x]
    end
  end
  return mf
end