Как мне написать общую функцию memoize?
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пишу функцию для поиска числа треугольника и естественный способ написать это рекурсивно:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Но попытка вычислить первые 100 000 чисел треугольника через некоторое время терпит неудачу из-за переполнения стека.Это идеальная функция для запоминать, но мне нужно решение, которое будет запоминать любую функцию, которую я ему передаю.
Решение
Могу поспорить, что-то вроде этого должно работать со списками переменных аргументов в 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).Фактически, вы даже можете придумать сценарий, в котором мемоизированная реализация будет иметь лучшую производительность, чем реализация в закрытой форме!
Вы также задаете неправильный вопрос для вашей первоначальной проблемы;)
Это лучший способ для этого случая:
треугольник(п) = п * (п - 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));
В 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 _)
Я не думаю, что это скомпилируется, но это иллюстрирует идею.
Обновлять:Комментаторы отметили, что мемоизация — хороший способ оптимизировать рекурсию.Признаюсь, я не задумывался об этом раньше, поскольку обычно работаю на языке (C#), где обобщенную мемоизацию построить не так уж и просто.Возьмите пост ниже, помня об этом.
Я думаю У Люка, вероятно, есть наиболее подходящее решение. к этой проблеме, но мемоизация, как правило, не является решением проблемы переполнения стека.
Переполнение стека обычно вызвано тем, что рекурсия идет глубже, чем может выдержать платформа.Языки иногда поддерживают "хвостовая рекурсия", который повторно использует контекст текущего вызова, а не создает новый контекст для рекурсивного вызова.Но многие основные языки/платформы этого не поддерживают.Например, в C# нет встроенной поддержки хвостовой рекурсии.64-битная версия .NET JITter может применять его в качестве оптимизации на уровне IL, что практически бесполезно, если вам нужна поддержка 32-битных платформ.
Если ваш язык не поддерживает хвостовую рекурсию, лучший вариант избежать переполнения стека — либо преобразовать в явный цикл (гораздо менее элегантно, но иногда необходимо), либо найти неитеративный алгоритм, такой как Люк, предложенный для этой проблемы.
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", так что это, наверное, нормально.
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
Этот вопрос вдохновил меня на реализацию (еще одной) гибкой функции запоминания в 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
Вот общая реализация 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;
};
}
}
(Цитата из статья в французском блоге)
В духе публикации мемоизации на разных языках я хотел бы ответить @onebyone.livejournal.com примером C++, не меняющим язык.
Во-первых, мемоайзер для функций с одним аргументом:
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_;
};
Просто создайте экземпляр мемомайзера, передайте ему свою функцию и аргумент.Просто убедитесь, что одна и та же заметка не используется двумя разными функциями (но вы можете использовать ее в разных реализациях одной и той же функции).
Далее функция драйвера и реализация.Только функция драйвера должна быть Public 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.Количество звонков измеряется для проверки правильности.(вставьте сюда модульный тест...)
Это запоминает только одну входную функцию.Обобщение для нескольких аргументов или различных аргументов оставлено в качестве упражнения для читателя.
В Perl легко получить общую мемоизацию.Модуль Memoize является частью ядра Perl и отличается высокой надежностью, гибкостью и простотой в использовании.
Пример из его man-страницы:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
Вы можете добавлять, удалять и настраивать запоминание функций. во время выполнения! Вы можете предоставить обратные вызовы для собственных вычислений сувениров.
В Memoize.pm даже есть возможность сделать кэш памяти постоянным, поэтому его не нужно заново заполнять при каждом вызове вашей программы!
Вот документация: http://perldoc.perl.org/5.8.8/Memoize.html
Видеть этот пост в блоге для общего решения Scala — до 4 аргументов.
Развивая идею, можно также запоминать функции с двумя входными параметрами:
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
Обратите внимание, что порядок параметров имеет значение в алгоритме кэширования, поэтому, если порядок параметров не имеет значения в функциях, подлежащих запоминанию, шансы на попадание в кеш будут увеличены за счет сортировки параметров перед проверкой кеша.
Но важно отметить, что некоторые функции невозможно сохранить в памяти.Я написал запомнить2 чтобы увидеть, является ли рекурсивный Евклидов алгоритм поиск наибольшего общего делителя можно ускорить.
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
Как выясняется из, НОД плохо реагирует на мемоизацию.Вычисления, которые он выполняет, гораздо менее затратны, чем алгоритм кэширования.Для больших чисел он завершается довольно быстро.Через некоторое время кэш становится очень большим.Этот алгоритм, вероятно, настолько быстр, насколько это возможно.
Рекурсия не нужна.Число n-го треугольника равно n(n-1)/2, поэтому...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Пожалуйста, не повторяйте это.Либо используйте формулу 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];
