optimization - ¿Cómo escribo una función de memoria genérica?
recursion lua (16)
Estoy escribiendo una función para encontrar números de triángulo y la forma natural de escribirlo es recursiva:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Pero intentar calcular los primeros 100.000 números de triángulo falla con un desbordamiento de pila después de un tiempo. Esta es una función ideal para memorizar , pero quiero una solución que memorice cualquier función que le pase.
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 artículo de blog francés )
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 currying puede hacer que funcione. El problema más sutil es que memoize(f) != memoize(f) para cualquier función f . Una manera muy furtiva de arreglar esto sería algo como lo siguiente:
val correctMem = memoize(memoize _)
No creo que esto compile, pero sí ilustra la idea.
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 la pila, el triángulo aún debe ser sembrado.
Apuesto a que algo así 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 puedas hacer algo inteligente con metatables con __tostring para que la lista de argumentos se convierta simplemente con un tostring (). Oh las posibilidades.
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
Tenga en cuenta que el orden de los parámetros importa en el algoritmo de almacenamiento en caché, por lo que si el orden de los parámetros no importa en las funciones que se van a memorizar, las probabilidades de obtener un golpe de caché aumentarán ordenando los parámetros antes de verificar el caché.
Pero es importante tener en cuenta que algunas funciones no pueden ser memorablemente rentables. Escribí memoize2 para ver si el algoritmo euclidiano recursivo para encontrar el mayor divisor común podía acelerarse.
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
Como resultado, 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 números grandes, termina bastante rápido. Después de un tiempo, el caché crece muy grande. Este algoritmo es probablemente tan rápido como puede ser.
En la línea de publicar memoraciones en diferentes idiomas, me gustaría responder a @ onebyone.livejournal.com con un ejemplo de C ++ que no cambia el idioma.
Primero, un memorando 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 crea una instancia del memoizer, dale tu función y argumento. Solo asegúrese de no compartir la misma nota entre dos funciones diferentes (pero puede 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 controlador debe ser pública int fib (int); // driver 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);
}
Enlace permanente que muestra la salida en codepad.org. El número de llamadas se mide para verificar la corrección. (inserte la prueba unitaria aquí ...)
Esto solo memoriza una de las funciones de entrada. Generalizando múltiples argumentos o variando los argumentos dejados como ejercicio para el lector.
Mathematica tiene una manera particularmente ingeniosa de hacer memoizaciones, basándose en el hecho de que los hash y las llamadas a funciones usan la misma sintaxis:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
Eso es. Funciona porque las reglas para las llamadas a funciones de coincidencia de patrones son tales que siempre usa una definición más específica antes de una definición más general.
Por supuesto, como se ha señalado, este ejemplo tiene una solución de forma cerrada: triangle[x_] := x*(x+1)/2 . Los números de Fibonacci son el ejemplo clásico de cómo la adición de memorando da una drástica aceleración:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Aunque también tiene un equivalente de forma cerrada, 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 memorización porque podría "simplemente usar un ciclo". El punto de memorización es que cualquier llamada a función repetida es O (1) tiempo. Eso es mucho mejor que O (n). De hecho, incluso podría inventar un escenario donde la implementación memoial tenga un mejor rendimiento que la implementación de forma cerrada.
En Perl la memorización 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 de memento personalizado.
Memoize.pm incluso tiene instalaciones para hacer que el memento cache sea persistente, por lo que no necesita ser rellenado en cada invocación de su programa.
Aquí está la documentación: http://perldoc.perl.org/5.8.8/Memoize.html
Vea esta publicación de blog para una solución genérica de Scala, hasta 4 argumentos.
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 sea correcto.
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 ha inspirado esta pregunta para implementar (otra más) función de memoria flexible en Lua.
https://github.com/kikito/memoize.lua
Ventajas principales:
- Acepta una cantidad variable de argumentos
- No usa tostring; en cambio, organiza el caché en una estructura de árbol, usando los parámetros para atravesarlo.
- Funciona perfectamente con funciones que devuelven valores múltiples .
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
En C # 3.0: para funciones recursivas, puede 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;
}
}
Entonces puedes crear una función de Fibonacci memorada 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));
La recursividad no es necesaria. El n-ésimo número de triángulo es n (n-1) / 2, entonces ...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Por favor no repita esto. Use la fórmula x * (x + 1) / 2 o simplemente itere los valores y memorice sobre la marcha.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
También está haciendo la pregunta incorrecta para su 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 memorización seguiría siendo un enfoque pobre aquí. Sería mejor que simplemente escribieras un bucle simple en este caso. Vea esta respuesta para una discusión más completa.
Actualización : los comentaristas han señalado que la memorización es una buena forma de optimizar la recursión. Es cierto que no había considerado esto antes, ya que generalmente trabajo en un lenguaje (C #) donde la memorización generalizada no es tan trivial de construir. Tome la publicación a continuación con ese grano de sal en mente.
Creo que Luke probablemente tiene la solución más adecuada para este problema, pero la memorización generalmente no es la solución a ningún problema de desbordamiento de pila.
El desbordamiento de pila generalmente es causado por recursiones que van más allá de lo que la plataforma puede manejar. Los lenguajes a veces admiten la " recursividad final ", que reutiliza el contexto de la llamada actual, en lugar de crear un nuevo contexto para la llamada recursiva. Pero muchos lenguajes / plataformas convencionales no son compatibles. C # no tiene soporte inherente para la recursividad de la cola, por ejemplo. La versión de 64 bits de .NET JITter puede aplicarlo como una optimización en el nivel IL, que es casi inútil si necesita admitir plataformas de 32 bits.
Si su idioma no es compatible con recursividad de cola, su mejor opción para evitar desbordamientos de pila es convertirlo en un bucle explícito (mucho menos elegante, pero a veces necesario), o encontrar un algoritmo no iterativo como Luke para este problema.