Come faccio a scrivere una funzione di memoize generica?
https://stackoverflow.com/questions/129877
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto scrivendo una funzione per trovare numeri triangolari e il modo naturale scriverlo è ricorsivamente:
function triangle (x)
if x == 0 then return 0 end
return x+triangle(x-1)
end
Ma il tentativo di calcolare i primi 100.000 triangoli non riesce con un overflow dello stack dopo un po '. Questa è la funzione ideale per memoize , ma desidero una soluzione che memorizzi qualsiasi funzione che le passo. .
Soluzione
Scommetto che qualcosa del genere dovrebbe funzionare con elenchi di argomenti variabili in 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
Probabilmente potresti anche fare qualcosa di intelligente con un metatables con __tostring in modo che l'elenco degli argomenti possa essere semplicemente convertito con un tostring (). Oh le possibilità.
Altri suggerimenti
Mathematica ha un modo particolarmente semplice di fare la memoizzazione, basandosi sul fatto che hash e chiamate di funzione usano la stessa sintassi:
triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]
Questo è tutto. Funziona perché le regole per le chiamate di funzione di corrispondenza dei modelli sono tali che utilizza sempre una definizione più specifica prima di una definizione più generale.
Naturalmente, come è stato sottolineato, questo esempio ha una soluzione a forma chiusa: triangle [x_]: = x * (x + 1) / 2 . I numeri di Fibonacci sono il classico esempio di come l'aggiunta della memoizzazione dia una drastica accelerazione:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Anche se anche questo ha un equivalente in forma chiusa, sebbene messier: http: //mathworld.wolfram. com / FibonacciNumber.html
Non sono d'accordo con la persona che ha suggerito che ciò era inappropriato per la memoizzazione perché potresti semplicemente "utilizzare un ciclo". Il punto della memoizzazione è che qualsiasi chiamata di funzione di ripetizione è O (1) tempo. È molto meglio di O (n). In effetti, potresti persino inventare uno scenario in cui l'implementazione memorizzata ha prestazioni migliori rispetto all'implementazione a forma chiusa!
Stai anche ponendo la domanda sbagliata per il tuo problema originale;)
Questo è un modo migliore per quel caso:
triangolo (n) = n * (n - 1) / 2
Inoltre, supponendo che la formula non avesse una soluzione così accurata, la memoisation sarebbe ancora un approccio scadente qui. In questo caso farebbe meglio a scrivere un semplice ciclo. Vedi questa risposta per una discussione più completa.
In C # 3.0 - per le funzioni ricorsive, puoi fare qualcosa del tipo:
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;
}
}
Quindi puoi creare una funzione di Fibonacci memorizzata in questo modo:
var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
In Scala (non testato):
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
}
}
}
Nota che questo funziona solo per le funzioni di arity 1, ma con il curry potresti farlo funzionare. Il problema più sottile è che memoize (f)! = Memoize (f) per qualsiasi funzione f . Un modo molto subdolo per risolvere questo problema potrebbe essere il seguente:
val correctMem = memoize(memoize _)
Non penso che questo verrà compilato, ma illustra l'idea.
Aggiorna : i commentatori hanno sottolineato che la memoization è un buon modo per ottimizzare la ricorsione. Devo ammetterlo, non l'avevo mai considerato prima, dato che generalmente lavoro in un linguaggio (C #) in cui la memoizzazione generalizzata non è così banale da costruire. Prendi il post qui sotto con in mente quel granello di sale.
Penso che Probabilmente Luke ha la soluzione più appropriata a questo problema, ma la memoizzazione non è generalmente la soluzione a qualsiasi problema di overflow dello stack.
L'overflow dello stack di solito è causato da una ricorsione più profonda di quella che la piattaforma è in grado di gestire. Le lingue a volte supportano " ricorsione della coda " ;, che riutilizza il contesto della chiamata corrente , piuttosto che creare un nuovo contesto per la chiamata ricorsiva. Ma molte lingue / piattaforme tradizionali non lo supportano. C # non ha alcun supporto intrinseco per la ricorsione della coda, per esempio. La versione a 64 bit di .NET JITter può applicarla come ottimizzazione a livello di IL, che è quasi inutile se è necessario supportare piattaforme a 32 bit.
Se la tua lingua non supporta la ricorsione della coda, la migliore opzione per evitare overflow dello stack è quella di convertire in un ciclo esplicito (molto meno elegante, ma a volte necessario), o trovare un algoritmo non iterativo come Luke previsto questo 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);
Nota che per evitare un overflow dello stack, il triangolo dovrebbe comunque essere seminato.
Ecco qualcosa che funziona senza convertire gli argomenti in stringhe.
L'unica avvertenza è che non è in grado di gestire un argomento nullo. Ma la soluzione accettata non è in grado di distinguere il valore nil dalla stringa " nil " , quindi probabilmente va bene.
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
Sono stato ispirato da questa domanda per implementare (ancora un'altra) funzione di memorizzazione flessibile in Lua.
https://github.com/kikito/memoize.lua
Vantaggi principali:
- Accetta un numero variabile di argomenti
- Non usa la tostrazione; invece organizza la cache in una struttura ad albero, usando i parametri per attraversarla.
- Funziona bene con funzioni che restituiscono valori multipli .
Incollando qui il codice come riferimento:
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
Ecco un'implementazione generica di C # 3.0, se potrebbe aiutare:
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;
};
}
}
(Citato da un articolo di blog francese )
Sulla scia della pubblicazione di memoization in diverse lingue, vorrei rispondere a @ onebyone.livejournal.com con un esempio C ++ che non cambia la lingua.
Innanzitutto, un memoizer per le singole funzioni 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_;
};
Basta creare un'istanza del memoizer, alimentare la tua funzione e argomento. Assicurati solo di non condividere lo stesso memo tra due diverse funzioni (ma puoi condividerlo tra diverse implementazioni della stessa funzione).
Successivamente, un driver functon e un'implementazione. solo la funzione del driver deve essere pubblica int fib (int); // autista int fib_ (int); // implementazione
Implemented:
int fib_(int n){
++total_ops;
if(n == 0 || n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
E il driver, per memorizzare
int fib(int n) {
static memoizer1<int,int> memo;
return memo(fib_, n);
}
Permalink che mostra l'output su codepad.org. Il numero di chiamate viene misurato per verificare la correttezza. (inserisci il test unitario qui ...)
Questo memorizza solo una delle funzioni di input. Generalizzando per più argomenti o vari argomenti lasciati come esercizio per il lettore.
In Perl la memoizzazione generica è facile da ottenere. Il modulo Memoize fa parte del core perl ed è altamente affidabile, flessibile e facile da usare.
L'esempio dalla sua manpage:
# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before
È possibile aggiungere, rimuovere e personalizzare la memorizzazione delle funzioni in fase di esecuzione! È possibile fornire richiamate per il calcolo del ricordo personalizzato.
Memoize.pm ha anche delle funzionalità per rendere persistente la cache di ricordo, quindi non è necessario riempire nuovamente ogni invocazione del tuo programma!
Ecco la documentazione: http://perldoc.perl.org/5.8.8 /Memoize.html
Vedi questo post sul blog per una soluzione Scala generica, fino a 4 argomenti.
Estendendo l'idea, è anche possibile memorizzare le funzioni con due parametri di input:
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
Si noti che l'ordine dei parametri è importante nell'algoritmo di memorizzazione nella cache, quindi se l'ordine dei parametri non ha importanza nelle funzioni da memorizzare, le probabilità di ottenere un hit nella cache sarebbero aumentate ordinando i parametri prima di controllare la cache.
Ma è importante notare che alcune funzioni non possono essere memorizzate proficuamente. Ho scritto memoize2 per vedere se il ricorsivo Algoritmo euclideo per trovare l'algoritmo il più grande divisore comune potrebbe essere accelerato.
function gcd (a, b)
if b == 0 then return a end
return gcd(b, a%b)
end
A quanto pare, gcd non risponde bene alla memoizzazione. Il calcolo che esegue è molto meno costoso dell'algoritmo di memorizzazione nella cache. Sempre per grandi numeri, termina abbastanza rapidamente. Dopo un po ', la cache diventa molto grande. Questo algoritmo è probabilmente il più veloce possibile.
La ricorsione non è necessaria. L'ennesimo numero del triangolo è n (n-1) / 2, quindi ...
public int triangle(final int n){
return n * (n - 1) / 2;
}
Per favore, non ricorrere a questo. Utilizza la formula x * (x + 1) / 2 o semplicemente itera i valori e memorizza mentre procedi.
int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
sum+=i;
memo[i] = sum;
}
return memo[n];
