Помогает ли использование функциональных языков против многократного вычисления значений?

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

Термин, который вы ищете здесь: Памятка :

В компьютерах запоминание - это Техника оптимизации используется в первую очередь ускорить компьютерные программы путем вызовы функций избегают повторения расчет результатов для предварительно обработанные входные данные.

Нет, функциональный язык не выполняет автоматическое запоминание. Вы можете реализовать это в них, но также и в C ++. Это правда, однако, что когда вы пишете чисто функциональный код (то есть без побочных эффектов), то запоминание становится проще. Некоторые динамические языки (например, Perl) имеют модули автоматического запоминания, которые могут легко запоминать любую функцию. Эта тема обсуждается в разделе Автоматическое запоминание статьи Википедии .

Например, вот наивный C ++ Фибоначчи:

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