如何编写通用memoize函数？

Question

我正在编写一个函数来查找三角形数字,并且以递归方式编写它的自然方式:

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

但是尝试计算前100,000个三角形数字会在一段时间后出现堆栈溢出而失败.这是一个理想的memoize函数,但我想要一个能够记忆我传递给它的任何函数的解决方案.

Answer 1

Mathematica有一种特别灵活的记忆方式,依赖哈希和函数调用使用相同语法的事实:

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

而已.它的工作原理是因为模式匹配函数调用的规则总是在更一般的定义之前使用更具体的定义.

当然,正如已经指出的那样,这个例子有一个封闭形式的解决方案:triangle[x_] := x*(x+1)/2.Fibonacci数字是添加memoization如何提供极大加速的典型示例:

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)要好很多.实际上,您甚至可以编写一个方案,其中memoized实现比闭包形式实现具有更好的性能!

Answer 2

你也问你原来问题的错误问题;)

对于这种情况,这是一种更好的方法:

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

此外,假设公式没有这样一个简洁的解决方案,那么备忘录在这里仍然是一个糟糕的方法.在这种情况下,你最好只编写一个简单的循环.有关更全面的讨论,请参阅此答案.

Answer 3

我打赌像这样的东西应该适用于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()转换.哦,可能性.

Answer 4

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

然后你可以创建一个memoized斐波那契函数,如下所示:

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