Semplice esempio per Erlang Memoizzazione

Question

Supponiamo di avere una funzione semplice, che può diventare piuttosto costoso per valori di grandi dimensioni:

fact(0) -> 1; 
fact(N) -> N * fact(N - 1). 

Dove posso trovare un semplice esempio di caching (o memoizing) i valori della funzionalità utilizzando dets?

Qualsiasi altro modo per una facile memorizzazione sarebbe molto apprezzato.

Answer 1

L'idea è che ogni volta che chiedi il tuo pesante calcolo pesante, controlli immediatamente nella cache se lo hai già valutato. In caso affermativo, è sufficiente restituire il valore memorizzato. In caso contrario, è necessario valutare il nuovo valore e memorizzarlo, prima di restituirlo all'utente finale.

A dict, invece di una tabella di dets, potrebbe funzionare anche.

(la seguente soluzione è testato)

-module(cache_fact). 

-export([init/0, fact/1]). 

init() -> 
    {ok, _} = dets:open_file(values, []). 

fact(N) -> 
    case dets:lookup(values, N) of 
     [] -> 
     Result = do_fact(N), 
     dets:insert_new(values, {N, Result}), 
     Result; 
     [{N, Cached}] -> 
     Cached 
    end. 

do_fact(0) -> 
    1; 
do_fact(N) -> 
    N * do_fact(N-1). 

si potrebbe desiderare di incapsulare il tutto in un Erlang generic server. Nella funzione init dovresti creare la tabella DETS, la funzione fact/1 dovrebbe rappresentare la tua API e dovresti implementare la logica nelle funzioni handle_call.

Un esempio migliore potrebbe essere la creazione di un servizio di riduzione degli URL per gli URL, memorizzato nella cache.

Come suggerito da @Zed, sarebbe opportuno memorizzare anche i risultati parziali per evitare ulteriori ricalcoli. Se questo è il caso:

-module(cache_fact). 

-export([init/0, fact/1]). 

init() -> 
    {ok, _} = dets:open_file(values, []). 

fact(0) -> 
    1; 
fact(N) -> 
    case dets:lookup(values, N) of 
     [] -> 
     Result = N * fact(N-1), 
     dets:insert_new(values, {N, Result}), 
     Result; 
     [{N, Cached}] -> 
     Cached 
    end. 

Ovviamente, anche se questo aiuta per i grandi numeri, è necessario considerare il costo aggiuntivo di aggiungere una voce alla tabella di ricerca per ogni passo. Considerando i motivi per cui è stata introdotta la memorizzazione nella cache (supponiamo che il calcolo sia molto pesante, quindi il tempo di inserimento della ricerca è insignificante), questo dovrebbe essere perfettamente soddisfacente.

Answer 2

A seconda del caso, è anche possibile utilizzare il process dictionary per Memoizzazione:

fact(0) -> 1; 
fact(N) -> 
    case erlang:get({'fact', N}) of 
     F when is_integer(F) -> 
      F; 
     'undefined' -> 
      F = N * fact(N-1), 
      erlang:put({'fact', N}, F), 
      F 
    end.