Как я пишу универсальную функцию memoize?

В Perl универсальный memoization легко получить. Модуль Memoize является частью ядра жемчуга и высоконадежен, гибок, и прост в использовании.

Пример от он - страница справочника:

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

Можно добавить, удалить и настроить memoization функций во время выполнения! Можно обеспечить обратные вызовы для пользовательского вычисления сувенира.

Memoize.pm даже имеет средства для того, чтобы сделать кэш сувенира персистентным, таким образом, он не должен быть снова наполнен на каждом вызове Вашей программы!

Вот документация: http://perldoc.perl.org/5.8.8/Memoize.html

Расширяя идею, это также возможно к функциям memoize с двумя входными параметрами:

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 не отвечает хорошо на memoization. Вычисление, которое это делает, является намного менее дорогим, чем алгоритм кэширования. Когда-либо для больших количеств, это завершается справедливо быстро. Через некоторое время кэш становится очень большим. Этот алгоритм, вероятно с такой скоростью, как это может быть.

В духе регистрации memoization на различных языках, я хотел бы ответить на @onebyone.livejournal.com с non-language-changing примером 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, подайте его Ваша функция и аргумент. Просто удостоверьтесь, что не совместно использовали ту же заметку между двумя различными функциями (но можно совместно использовать ее между различными реализациями той же функции).

Затем, функция драйвера и реализация. только функция драйвера должна быть общедоступной международной выдумкой (интервал);//интервал драйвера выдумывают _ (интервал);//реализация

Реализованный:

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

И драйвер, к memoize

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

Показ постоянной ссылки производится на codepad.org. Количество вызовов измеряется для проверки правильности. (вставьте модульный тест здесь...),

Это только memoizes функции ввода. Обобщение для нескольких args или переменных аргументов, оставленных как осуществление для читателя.

Вот универсальная реализация 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;

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

(Заключенный в кавычки из французской статьи блога)

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

Обратите внимание, что для предотвращения переполнения стека треугольник должен был бы все еще быть отобран.

В (непротестированном) 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, но с приправлением карри Вас мог заставить его работать. Более тонкая проблема - это memoize(f) != memoize(f) для любой функции f. Один очень подлый способ зафиксировать это был бы чем-то как следующее:

val correctMem = memoize(memoize _)

Я не думаю, что это скомпилирует, но это действительно иллюстрирует идею.

Вы также задаете неправильный вопрос для своей исходной проблемы ;)

Это - лучший путь к тому случаю:

треугольник (n) = n * (n - 1) / 2

Кроме того, предположение формулы не имело такого аккуратного решения, memoisation все еще будет плохим подходом здесь. Вы были бы более обеспечены просто запись простого цикла в этом случае. См. этот ответ для более полного обсуждения.

Обновление: Комментаторы указали, что memoization является хорошим способом оптимизировать рекурсию. По общему признанию я не рассмотрел это прежде, так как я обычно работаю на языке (C#), где обобщено memoization, не таким образом тривиален для создания. Займите пост ниже с той мелкой частицей соли в памяти.

Я думаю, что у Luke, вероятно, есть наиболее подходящее решение к этой проблеме, но memoization обычно не является решением никакой проблемы переполнения стека.

Переполнение стека обычно вызывается рекурсией, идущей глубже, чем платформа может обработать. Языки иногда поддерживают "хвостовую рекурсию", которая снова использует контекст текущего вызова, вместо того, чтобы создать новый контекст для рекурсивного вызова. Но много основных языков/платформ не поддерживает это. C# не имеет никакой свойственной поддержки хвостовой рекурсии, например. 64-разрядная версия Дрожания.NET может применить его как оптимизацию на уровне IL, который почти бесполезен, если необходимо поддерживать 32-разрядные платформы.

Если Ваш язык не поддерживает хвостовую рекурсию, Ваш наилучший вариант для предотвращения переполнений стека состоит в том, чтобы или преобразовать в явный цикл (намного менее изящный, но иногда необходимый), или найти, что неитеративный алгоритм, такой как Luke предусмотрел эту проблему.

Mathematica имеет особенно гладкий способ сделать memoization, полагаясь на то, что хеши и вызовы функции используют тот же синтаксис:

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

Именно. Это работает, потому что правила для вызовов функции сопоставления с образцом таковы, что это всегда использует более определенное определение перед более общим определением.

Конечно, как был указан, этот пример имеет решение закрытой формы: triangle[x_] := x*(x+1)/2. Числа Фибоначчи являются классическим примером того, как добавление memoization дает решительное ускорение:

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

Хотя это также имеет эквивалентную закрытую форму, хотя более грязный: http://mathworld.wolfram.com/FibonacciNumber.html

Я не соглашаюсь с человеком, который предположил, что это было несоответствующим для memoization, потому что Вы могли "просто использовать цикл". Точка memoization - то, что любые повторные вызовы функции являются O (1) время. Это намного лучше, чем O (n). На самом деле Вы могли даже придумать сценарий, где мемоизованная реализация имеет лучшую производительность, чем реализация закрытой формы!