ejemplo simple para Erlang memoization

Question

Suponga que tiene una función simple, que puede llegar a ser muy caro para grandes valores:

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

¿Dónde puedo encontrar un ejemplo sencillo de almacenamiento en caché (o memoizing) valores de la función mediante el uso de dets?

Cualquier otra forma de memorizar fácilmente sería muy apreciada.

Answer 1

La idea es que cada vez que solicite su cálculo pesado de, inmediatamente verifica la memoria caché si ya la ha evaluado. En caso afirmativo, simplemente devuelve el valor almacenado. De lo contrario, debe evaluar el nuevo valor y almacenarlo antes de devolverlo al usuario final.

A dict, en lugar de una tabla de dets, también podría funcionar.

(la siguiente solución es no probado)

-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). 

Es posible que desee encapsular todo el asunto en una Erlang generic server. En la función init debe crear la tabla DETS, la función fact/1 debe representar su API y debe implementar la lógica en las funciones handle_call.

Un mejor ejemplo podría ser escribir un servicio abreviado para URL, en caché.

Según lo sugerido por @Zed, tendría sentido almacenar los resultados parciales para evitar nuevos cálculos. Si este es el 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. 

Obviamente, incluso si esto ayuda para un gran número, usted tiene que considerar el costo adicional de añadir una entrada a la tabla de consulta para cada paso. Teniendo en cuenta los motivos por los que se ha introducido el almacenamiento en caché (suponemos que el cálculo es muy pesado, por lo que el tiempo de inserción de búsqueda es insignificante), esto debería ser perfectamente correcto.

Answer 2

Dependiendo de su caso, también se puede utilizar el process dictionary para memoization:

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.