使用函数式语言是否有助于反复计算值？

Question

考虑函数f(x,y):

f(x,0) = x*x;
f(0,y) = y*(y + 1);
f(x,y) = f(x,y-1) + f(x-1,y);

如果试图以某种语言(如C++)递归地实现它,他将遇到问题.

假设首先使用x = x0和调用该函数y = y0.然后对于任何对(x,y),其中0 <= x < x0和0 <= y < y0中间值将被多次计算 - 递归调用将形成一个巨大的树,其中多个叶子实际上将包含相同的对(x,y).对于对(x,y),其中x和y都接近于0,将多次计算值.

举例来说,我测试了类似的功能在C++实现的-为x=20和y=20(!是的,四地球小时),其计算大约需要4小时.

显然,可以以不重复计算的方式重写实现 - 迭代地或使用高速缓存表.

问题是:在递归实现上述函数时,函数式语言会更好地执行并避免重复计算吗？

Answer 1

你在这里寻找的术语是Memoization:

在计算中,memoization是一种优化技术,主要用于通过函数调用来避免重复计算先前处理的输入的结果来加速计算机程序.

不,功能语言不会自动实现memoization.您可以在它们中实现它,但也可以在C++中实现它.但是,当你编写纯粹的功能代码(即没有副作用)时,记忆就更容易了.一些动态语言(例如Perl)具有自动记忆模块,可以轻松记忆任何功能.维基百科文章的自动记忆部分讨论了这个主题.

例如,这是一个天真的C++ Fibonacci:

long fib_rec(long index)
{
    if (index < 2)
        return index;
    else
        return fib_rec(index - 1) + fib_rec(index - 2);
}

这是一个记忆版本:

long fib_memoized_aux(vector<long>& cache, long index)
{
    if (cache[index] >= 0)
    return cache[index];

    cache[index] = fib_memoized_aux(cache, index - 1) + fib_memoized_aux(cache, index - 2);
    return cache[index];
}


long fib_memoized(long index)
{
    vector<long> cache(index + 1, -1);
    cache[0] = 0;
    cache[1] = 1;

    return fib_memoized_aux(cache, index);
}