¿Cómo escribo una función memoize genérica?
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy escribiendo una función para encontrar números de triángulos y la forma natural Escribirlo es recursivamente:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Pero al intentar calcular los primeros 100,000 números de triángulos falla con un desbordamiento de pila después de un tiempo. Esta es una función ideal para memoize , pero quiero una solución que memorice cualquier función que le pase. .
Solución
Apuesto a que algo como esto debería funcionar con listas de argumentos variables en 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
Probablemente también podrías hacer algo inteligente con metatables con __tostring para que la lista de argumentos se pueda convertir con un tostring (). Oh las posibilidades.
Otros consejos
Mathematica tiene una forma particularmente ingeniosa de realizar la memorización, confiando en el hecho de que los hashes y las llamadas de función utilizan la misma sintaxis:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
Eso es todo. Funciona porque las reglas para las llamadas de función de coincidencia de patrones son tales que siempre usa una definición más específica antes que una definición más general.
Por supuesto, como se ha señalado, este ejemplo tiene una solución de forma cerrada: triángulo [x_]: = x * (x + 1) / 2 . Los números de Fibonacci son el ejemplo clásico de cómo agregar memoización da una aceleración drástica:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Aunque eso también tiene un formato cerrado, aunque más desordenado: http: //mathworld.wolfram. com / FibonacciNumber.html
No estoy de acuerdo con la persona que sugirió que esto no era apropiado para la memoria porque podría "usar un bucle". El punto de la memoria es que cualquier llamada repetida a la función es O (1). Eso es mucho mejor que O (n). De hecho, incluso podría inventar un escenario en el que la implementación memorizada tenga un mejor rendimiento que la implementación de forma cerrada.
También estás haciendo la pregunta incorrecta para tu problema original;) ??
Esta es una mejor manera para ese caso:
triángulo (n) = n * (n - 1) / 2
Además, suponiendo que la fórmula no tuviera una solución tan clara, la memoisación todavía sería un enfoque pobre aquí. Sería mejor que escribieras un simple bucle en este caso. Consulte esta respuesta para una discusión más completa.
En C # 3.0: para las funciones recursivas, puedes hacer 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;
}
}
Luego puede crear una función de Fibonacci memoized como esta:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
En Scala (no probado):
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
}
}
}
Tenga en cuenta que esto solo funciona para las funciones de arity 1, pero con el curry puede hacer que funcione. El problema más sutil es que memoize (f)! = Memoize (f) para cualquier función f . Una forma muy astuta de solucionar esto sería algo como lo siguiente:
val correctMem = memoize(memoize _)
No creo que esto se compile, pero ilustra la idea.
Actualización : los comentaristas han señalado que la memorización es una buena manera de optimizar la recursión. Es cierto que no había considerado esto antes, ya que generalmente trabajo en un lenguaje (C #) donde la memoria generalizada no es tan trivial de construir. Toma el post de abajo con ese grano de sal en mente.
Creo que Luke probablemente tenga la solución más adecuada a este problema, pero la memorización no es generalmente la solución a cualquier problema de desbordamiento de pila.
El desbordamiento de pila generalmente se debe a que la recursión va más allá de lo que la plataforma puede manejar. En ocasiones, los idiomas admiten " tail recursion " ;, que reutiliza el contexto de la llamada actual , en lugar de crear un nuevo contexto para la llamada recursiva. Pero una gran cantidad de lenguajes / plataformas convencionales no son compatibles con esto. C # no tiene soporte inherente para la recursión de la cola, por ejemplo. La versión de 64 bits de .NET JITter puede aplicarla como una optimización a nivel de IL, que es casi inútil si necesita soportar plataformas de 32 bits.
Si su idioma no admite la recursión de cola, su mejor opción para evitar los desbordamientos de pila es convertirlo en un bucle explícito (mucho menos elegante, pero a veces necesario), o encontrar un algoritmo no iterativo como el que proporcionó Luke. 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);
Tenga en cuenta que para evitar un desbordamiento de pila, aún sería necesario sembrar el triángulo.
Aquí hay algo que funciona sin convertir los argumentos en cadenas.
La única advertencia es que no puede manejar un argumento nulo. Pero la solución aceptada no puede distinguir el valor nil de la cadena " nil " , por lo que probablemente esté bien.
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
Me inspiró esta pregunta para implementar (otra función más flexible) de memoria en Lua.
https://github.com/kikito/memoize.lua
Principales ventajas:
- Acepta un número variable de argumentos
- No utiliza tostring; en su lugar, organiza el caché en una estructura de árbol, utilizando los parámetros para atravesarlo.
- Funciona bien con funciones que devuelven múltiples valores .
Pegando el código aquí como referencia:
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
Aquí hay una implementación genérica de C # 3.0, si pudiera ayudar:
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 un blog francés artículo )
En la línea de publicación de memorias en diferentes idiomas, me gustaría responder a @ onebyone.livejournal.com con un ejemplo de C ++ que no cambia de idioma.
Primero, un memoizer para funciones arg individuales:
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_;
};
Simplemente cree una instancia del memoizer, aliméntelo con su función y argumento. Solo asegúrate de no compartir la misma nota entre dos funciones diferentes (pero puedes compartirla entre diferentes implementaciones de la misma función).
A continuación, una función de controlador y una implementación. Solo la función del conductor debe ser pública. int fib (int); // conductor int fib_ (int); // implementación
Implementado:
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
Y el conductor, para memorizar
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Permalink mostrando la salida en codepad.org. El número de llamadas se mide para verificar la exactitud. (inserte la prueba de la unidad aquí ...)
Esto solo memoriza las funciones de una entrada. Generalización para múltiples argumentos o argumentos variables dejados como un ejercicio para el lector.
En Perl, la memoria genérica es fácil de obtener. El módulo Memoize es parte del núcleo de Perl y es altamente confiable, flexible y fácil de usar.
El ejemplo de su página de manual:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
¡Puede agregar, eliminar y personalizar la memorización de funciones en tiempo de ejecución! Puede proporcionar devoluciones de llamada para el cálculo personalizado de memento.
Memoize.
Aquí está la documentación: http://perldoc.perl.org/5.8.8 /Memoize.html
Consulte esta publicación de blog para obtener una solución Scala genérica, hasta 4 argumentos.
Extendiendo la idea, también es posible memorizar funciones con dos 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 el orden de los parámetros es importante en el algoritmo de almacenamiento en caché, por lo tanto, si el orden de los parámetros no importa en las funciones que se deben memorizar, las probabilidades de obtener un cache se incrementarán al ordenar los parámetros antes de verificar la caché.
Pero es importante tener en cuenta que algunas funciones no se pueden memorizar de forma rentable. Escribí memoize2 para ver si el algoritmo euclidiano recursivo para encontrar el el mayor divisor común podría acelerarse.
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
Resulta que gcd no responde bien a la memorización. El cálculo que hace es mucho menos costoso que el algoritmo de almacenamiento en caché. Siempre para grandes números, termina bastante rápido. Después de un tiempo, el caché crece muy grande. Este algoritmo es probablemente lo más rápido que puede ser.
La recursión no es necesaria. El número del triángulo n es n (n-1) / 2, así que ...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Por favor, no repitan esto. Utilice la fórmula x * (x + 1) / 2 o simplemente itere los valores y memorice a medida que avanza.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
