Как мне написать универсальную функцию памятки?
Я пишу функцию, чтобы найти номера треугольника, и естественный способ написать это рекурсивно:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Но попытка вычислить первые 100 000 чисел треугольника терпит неудачу с переполнением стека через некоторое время. Это идеальная функция для запоминания, но я хочу решение, которое запомнит любую функцию, которую я передам ей.
16 ответов
Могу поспорить, что-то вроде этого должно работать со списками переменных аргументов в 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 имеет очень удобный способ создания заметок, опираясь на тот факт, что хеши и вызовы функций используют один и тот же синтаксис:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
Вот и все. Это работает, потому что правила для вызовов функций сопоставления с образцом таковы, что он всегда использует более конкретное определение перед более общим определением.
Конечно, как было указано, этот пример имеет решение в закрытой форме: triangle[x_] := x*(x+1)/2, Числа Фибоначчи являются классическим примером того, как добавление мемоизации дает резкое ускорение:
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). Фактически, вы могли бы даже придумать сценарий, в котором запомненная реализация имеет лучшую производительность, чем реализация в закрытой форме!
Вы также задаете неправильный вопрос для вашей первоначальной проблемы;)
Это лучший способ для этого случая:
треугольник (n) = n * (n - 1) / 2
Кроме того, предполагая, что формула не имеет такого аккуратного решения, запоминание все равно будет плохим подходом. В этом случае вам лучше написать простой цикл. Смотрите этот ответ для более полного обсуждения.
В 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;
}
}
Затем вы можете создать запомненную функцию Фибоначчи следующим образом:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
Обновление: комментаторы отметили, что запоминание является хорошим способом оптимизации рекурсии. По общему признанию, я не рассматривал это прежде, так как я обычно работаю на языке (C#), где обобщенное запоминание не так тривиально построить. Возьмите пост ниже, имея в виду это зерно соли.
Я думаю, что у Люка, вероятно, есть наиболее подходящее решение этой проблемы, но, как правило, запоминание не является решением любой проблемы переполнения стека.
Переполнение стека обычно вызвано тем, что рекурсия идет глубже, чем может выдержать платформа. Языки иногда поддерживают " хвостовую рекурсию", которая повторно использует контекст текущего вызова, а не создает новый контекст для рекурсивного вызова. Но многие основные языки / платформы не поддерживают это. Например, в C# отсутствует встроенная поддержка хвостовой рекурсии. 64-разрядная версия.NET JITter может применять ее в качестве оптимизации на уровне IL, что практически бесполезно, если вам требуется поддержка 32-разрядных платформ.
Если ваш язык не поддерживает хвостовую рекурсию, лучшим способом избежать переполнения стека является либо преобразование в явный цикл (гораздо менее элегантный, но иногда необходимый), либо поиск не итеративного алгоритма, такого как Люк, для этой проблемы.
В 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
}
}
}
Обратите внимание, что это работает только для функций arity 1, но с помощью curry вы можете заставить это работать. Более тонкая проблема заключается в том, что memoize(f) != memoize(f) для любой функции f, Один очень хитрый способ исправить это будет примерно так:
val correctMem = memoize(memoize _)
Я не думаю, что это скомпилируется, но это иллюстрирует идею.
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);
Обратите внимание, что во избежание переполнения стека треугольник все равно должен быть засеян.
Этот вопрос вдохновил меня на реализацию (еще одной) гибкой функции памятки в Lua.
https://github.com/kikito/memoize.lua
Основные преимущества:
- Принимает переменное количество аргументов
- Не использует tostring; вместо этого он организует кэш в древовидной структуре, используя параметры для его обхода.
- Прекрасно работает с функциями, которые возвращают несколько значений.
Вставка кода здесь в качестве ссылки:
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
Вот кое-что, что работает без преобразования аргументов в строки. Единственное предостережение в том, что он не может обработать нулевой аргумент. Но принятое решение не может отличить ценность 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
Вот общая реализация 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;
};
}
}
(Цитата из французской статьи в блоге)
В Perl обобщенную памятку легко получить. Модуль Memoize является частью ядра Perl и отличается высокой надежностью, гибкостью и простотой в использовании.
Пример из его справочной страницы:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
Вы можете добавлять, удалять и настраивать запоминание функций во время выполнения! Вы можете предоставить обратные вызовы для пользовательских вычислений сувениров.
Memoize.pm даже имеет средства для сохранения кэша memento, поэтому его не нужно перезаписывать при каждом вызове вашей программы!
Вот документация: http://perldoc.perl.org/5.8.8/Memoize.html
Смотрите этот пост в блоге для общего решения Scala, до 4 аргументов.
В духе публикации заметок на разных языках я хотел бы ответить на @onebyone.livejournal.com с примером C++ без изменения языка.
Во-первых, памятка для отдельных функций 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_;
};
Просто создайте экземпляр памятки, передайте ему свою функцию и аргумент. Просто убедитесь, что вы не разделяете одну и ту же заметку между двумя разными функциями (но вы можете поделиться ею между разными реализациями одной и той же функции).
Далее, функция драйвера и реализация. только функция драйвера должна быть публичной 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);
}
И водитель, чтобы запомнить
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Постоянная ссылка, показывающая вывод на codepad.org. Количество звонков измеряется для проверки правильности. (вставьте тестовый модуль здесь...)
Это запоминает только одну функцию ввода. Обобщение для нескольких аргументов или различных аргументов оставлено в качестве упражнения для читателя.
Рекурсия не нужна. Число n-го треугольника равно n(n-1)/2, так что...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Расширяя идею, можно также запоминать функции с двумя входными параметрами:
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 плохо реагирует на запоминание. Это вычисление намного дешевле, чем алгоритм кэширования. Когда-либо для больших чисел, это заканчивается довольно быстро. Через некоторое время кеш становится очень большим. Этот алгоритм, вероятно, так быстро, как может быть.
Пожалуйста, не повторяйте это. Либо используйте формулу x*(x+1)/2, либо просто повторяйте значения и запоминайте их по ходу дела.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];