Я пишу функцию, чтобы найти числа треугольников, и естественный способ ее записи рекурсивно:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Но попытка вычислить первые 100 000 номеров треугольников завершится неудачей с переполнением стека через некоторое время. Это идеальная функция для memoize, но я хочу решение, которое будет memoize любую функцию, которую я передаю ему.
Держу пари, что-то вроде этого должно работать с переменными списками аргументов в 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(). О возможности.
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]
Хотя это тоже имеет эквивалент закрытой формы, хотя и messier: http://mathworld.wolfram.com/FibonacciNumber.html
Я не согласен с человеком, который предположил, что это не подходит для memoization, потому что вы можете "просто использовать цикл". Пункт memoization заключается в том, что любые вызовы с повторными функциями - это время O (1). Это намного лучше, чем O (n). Фактически, вы даже можете придумать сценарий, в котором memoized реализация имеет лучшую производительность, чем реализация закрытой формы!
Вы также задаете неправильный вопрос для своей исходной проблемы;)
Это лучший способ для этого случая:
треугольник (n) = n * (n - 1)/2
Кроме того, полагая, что у формулы не было такого опрятного решения, мемуазия по-прежнему будет плохой подход здесь. В этом случае вам будет лучше написать простой цикл. См. этот ответ для более полного обсуждения.
В С# 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 функцию Fibonacci следующим образом:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
В Scala (untested):
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, но с currying вы можете заставить его работать. Более тонкая проблема заключается в том, что memoize(f) != memoize(f) для любой функции f. Один очень хитрый способ исправить это будет выглядеть примерно так:
val correctMem = memoize(memoize _)
Я не думаю, что это скомпилируется, но это иллюстрирует идею.
Обновление: комментаторы отметили, что memoization - хороший способ оптимизации рекурсии. По общему признанию, я не рассматривал это раньше, так как я обычно работаю на языке (С#), где обобщенная memoization не так тривиально строить. Возьмите пост ниже с этим зерном соли в виду.
Я думаю, Luke, вероятно, имеет наиболее подходящее решение для этой проблемы, но memoization обычно не является решением какой-либо проблемы.
Переполнение стека обычно вызвано тем, что рекурсия идет глубже, чем может обрабатывать платформа. Языки иногда поддерживают " tail recursion", которая повторно использует контекст текущего вызова, а не создает новый контекст для рекурсивного вызова. Но многие основные языки/платформы не поддерживают это. Например, у С# нет встроенной поддержки хвостовой рекурсии. 64-разрядная версия .NET JITter может применять ее как оптимизацию на уровне IL, что почти бесполезно, если вам необходимо поддерживать 32-разрядные платформы.
Если ваш язык не поддерживает хвостовую рекурсию, лучшим вариантом для избежания является либо преобразование в явный цикл (гораздо менее элегантный, но иногда необходимый), либо поиск неитеративного алгоритма, такого как Luke для эта проблема.
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);
Обратите внимание, что чтобы избежать, треугольник все равно должен быть посеян.
Здесь что-то работает без преобразования аргументов в строки.
Единственное предостережение в том, что он не может справиться с аргументом 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
Я был вдохновлен этим вопросом для реализации (еще одной) гибкой функции memoize в Lua.
https://github.com/kikito/memoize.lua
Основные преимущества:
Вставка кода здесь в качестве ссылки:
local globalCache = {}
local function getFromCache(cache, args)
local node = cache
for i=1, #args do
if not node.children then return {} end
node = node.children[args[i]]
if not node then return {} end
end
return node.results
end
local function insertInCache(cache, args, results)
local arg
local node = cache
for i=1, #args do
arg = args[i]
node.children = node.children or {}
node.children[arg] = node.children[arg] or {}
node = node.children[arg]
end
node.results = results
end
-- public function
local function memoize(f)
globalCache[f] = { results = {} }
return function (...)
local results = getFromCache( globalCache[f], {...} )
if #results == 0 then
results = { f(...) }
insertInCache(globalCache[f], {...}, results)
end
return unpack(results)
end
end
return memoize
Вот общая реализация С# 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;
};
}
}
(Цитируется из статья французского блога)
В духе публикации memoization на разных языках, я бы хотел ответить на @onebyone.livejournal.com с помощью языка С++, не меняющего языка.
Во-первых, memoizer для отдельных функций 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_;
};
Просто создайте экземпляр memoizer, подайте ему свою функцию и аргумент. Просто убедитесь, что вы не разделяете одну и ту же заметку между двумя различными функциями (но вы можете поделиться ею между различными реализациями одной и той же функции).
Далее, функтор драйвера и реализация. только функция драйвера должна быть общедоступной 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);
}
И драйвер, memoize
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Постоянная ссылка на вывод на codepad.org. Количество звонков измеряется для проверки правильности. (вставьте unit test здесь...)
Это только запоминает одну функцию ввода. Обобщение для нескольких аргументов или переменных аргументов, оставленных как упражнение для читателя.
В Perl обобщенная memoization легко получить. Модуль Memoize является частью ядра perl и обладает высокой надежностью, гибкостью и простотой в использовании.
Пример из него manpage:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
Вы можете добавлять, удалять и настраивать memoization функций во время выполнения! Вы можете предоставить обратные вызовы для пользовательских memento-вычислений.
Memoize.pm даже имеет возможности для сохранения кеша памяти, поэтому его не нужно переполнять при каждом вызове вашей программы!
Здесь документация: http://perldoc.perl.org/5.8.8/Memoize.html
Смотрите это сообщение в блоге для общего решения Scala, до 4 аргументов.
Расширяя идею, можно также 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 плохо реагирует на воспоминание. Расчет, который он делает, намного дешевле, чем алгоритм кэширования. Когда-либо для больших чисел, он заканчивается довольно быстро. Через некоторое время кеш становится очень большим. Этот алгоритм, вероятно, так же быстро, как и может быть.
Рекурсия не требуется. N-е число треугольников - n (n-1)/2, поэтому...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Пожалуйста, не повторяйте это. Используйте либо формулу x * (x + 1)/2, либо просто перебирайте значения и сохраняйте memoize, когда вы идете.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];