Como posso escrever uma função memoize genérico?
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou escrevendo uma função para encontrar números triângulo e a maneira natural para escrever é recursiva:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Mas a tentativa de calcular os primeiros 100.000 números triângulo falha com um estouro de pilha depois de um tempo. Esta é uma função ideal para memoize , mas eu quero uma solução que irá memoize qualquer função que eu passar para ele .
Solução
I aposta algo como isso deve trabalhar com listas de argumentos variáveis ??na 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
Você provavelmente também poderia fazer algo inteligente com um metatables com __tostring para que a lista de argumentos poderia apenas ser convertido com um tostring (). Oh as possibilidades.
Outras dicas
Mathematica tem uma forma particularmente escorregadia fazer memoization, contando com o fato de que hashes e chamadas de função usar a mesma sintaxe:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
É isso. Ele funciona porque as regras para chamadas de função de correspondência de padrão são tais que sempre usa uma definição mais específica antes de uma definição mais geral.
Claro que, como tem sido apontado, este exemplo tem uma solução de forma fechada: triangle[x_] := x*(x+1)/2. números de Fibonacci são o exemplo clássico de como a adição de memoization dá uma aceleração drástica:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Embora isso também tem uma forma fechada equivalente, ainda mais confusa: http: //mathworld.wolfram. com / FibonacciNumber.html
Não concordo com a pessoa que sugeriu este era impróprio para memoization porque você poderia "apenas usar um loop". O ponto de memoization é que todas as chamadas função de repetição são O (1) tempo. Isso é muito melhor do que O (n). Na verdade, você pode até mesmo inventar um cenário onde a implementação memoized tem melhor desempenho do que a implementação de forma fechada!
Você também está fazendo a pergunta errada para o seu problema original;) ??
Esta é a melhor maneira para esse caso:
triângulo (n) = n * (n - 1) / 2
Além disso, supondo que a fórmula não tinha uma tal solução puro, memoisation ainda seria uma abordagem pobre aqui. Você seria melhor fora de apenas escrever um loop simples neste caso. Consulte esta resposta para uma discussão mais completa.
Em C # 3.0 - para funções recursivas, você pode fazer algo como:
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;
}
}
Em seguida, você pode criar uma função Fibonacci memoized assim:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
Em Scala (não testado):
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
}
}
}
Note que isto só funciona para as funções de aridade 1, mas com currying você poderia fazê-lo funcionar. O problema mais sutil é que memoize(f) != memoize(f) para qualquer função f. Uma maneira muito sorrateiro para corrigir isso seria algo como o seguinte:
val correctMem = memoize(memoize _)
Eu não acho que isso vai compilar, mas serve para ilustrar a idéia.
Atualizar : Commenters têm apontado que memoization é uma boa maneira de recursão otimizar. Evidentemente, eu não tinha considerado isso antes, desde que eu geralmente trabalho em uma linguagem (C #), onde memoization generalizado não é tão trivial para construir. Leve o post abaixo com aquele grão de sal em mente.
Luke provavelmente tem a solução mais adequada para este problema, mas memoization geralmente não é a solução para qualquer problema de estouro de pilha.
estouro de pilha normalmente é causado por recursão vai mais profunda do que a plataforma pode manipular. Línguas, por vezes, suportar " cauda recursão ", que reutiliza o contexto da chamada atual, em vez do que criar um novo contexto para a chamada recursiva. Mas um monte de línguas dominantes / plataformas não suportam isso. C # não tem suporte inerente para a cauda-recursão, por exemplo. A versão do .NET jitter de 64 bits pode aplicá-la como uma otimização no nível do IL, que é tudo, mas inútil se você precisa para suportar plataformas de 32 bits.
Se o seu idioma não suporta cauda recursão, a sua melhor opção para evitar pilha transborda ou é para converter em um loop explícita (muito menos elegante, mas às vezes necessário), ou encontrar um algoritmo não-interativo, como Luke prevista este problema.
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);
Note que, para evitar um estouro de pilha, triângulo ainda precisa ser semeado.
Há algo aqui que funciona sem converter os argumentos para strings.
A única ressalva é que ele não pode lidar com um argumento nulo. Mas a solução aceita não pode distinguir o valor nil do "nil" corda, de modo que é provavelmente OK.
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
Eu fui inspirado por esta questão de implementar (mais um) função memoize flexível na Lua.
https://github.com/kikito/memoize.lua
Principais vantagens:
- aceita um número variável de argumentos
- Não usa tostring; em vez disso, ele organiza o cache em uma estrutura de árvore, usando os parâmetros para atravessá-lo.
- funciona muito bem com as funções que o retorno vários valores .
Como colar o código aqui como referência:
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
Aqui é um genérico C # 3.0 implementação, se ele poderia ajudar:
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;
};
}
}
(Citado de um french artigo de blog )
Na veia de memoization postagem em diferentes línguas, eu gostaria de responder a @ onebyone.livejournal.com com um C ++ exemplo-não-linguagem mudando.
Primeiro, uma memoizer para funções arg individuais:
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_;
};
Basta criar uma instância da memoizer, alimentá-lo com a sua função e argumento. Apenas certifique-se de não compartilhar o mesmo memorando entre duas funções diferentes (mas você pode compartilhá-lo entre diferentes implementações da mesma função).
Em seguida, uma functon motorista, e uma implementação. apenas a função de motorista precisa ser pública fib int (int); // motorista fib_ int (int); // implementação
Implementado:
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
E o motorista, para memoize
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Link permanente mostrando saída no codepad.org. Número de chamadas é medida para verificar a exatidão. (Inserir teste de unidade aqui ...)
Isso só memoizes um funções de entrada. Generalizando para vários argumentos ou diferentes argumentos deixado como um exercício para o leitor.
Em Perl memoization genérico é fácil de obter. O módulo Memoize faz parte do núcleo Perl e é altamente fiável, flexível, e de fácil utilização.
O exemplo dela é manpage:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
Você pode adicionar, remover e memoization personaliza de funções em tempo de execução! Você pode fornecer retornos de chamada para computação lembrança personalizada.
Memoize.pm ainda tem comodidades para preparar o memento cache persistente, para que ele não precisa estar em cada invocação de seu programa cheio de re!
Aqui está a documentação: http://perldoc.perl.org/5.8.8 /Memoize.html
este post para uma solução Scala genérico, até 4 argumentos.
Estendendo a idéia, também é possível memoize funções com dois parâmetros de entrada:
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
Observe que as questões de ordem parâmetro no algoritmo de cache, por isso, se ordem parâmetro não importa nas funções que irão ser memoized as chances de conseguir um acerto de cache seria aumentado, classificando os parâmetros antes de verificar o cache.
Mas é importante notar que algumas funções não podem ser proveitosamente memoized. Eu escrevi memoize2 para ver se o recursiva euclidiana algoritmo para encontrar o maior divisor comum poderia ser acelerado.
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
Como se vê, gcd não respondem bem a memoization. O cálculo que ele faz é muito menos dispendioso do que o algoritmo de cache. Nunca para grandes números, ele termina com bastante rapidez. Depois de um tempo, o cache cresce muito grande. Este algoritmo é provavelmente tão rápido quanto ele pode ser.
A recursão não é necessário. O número triângulo enésimo é n (n-1) / 2, então ...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Por favor, não recurse isso. Ou usar o x * (x + 1) / 2 fórmula ou simplesmente iterate os valores e memoize que você vá.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
