Простой пример для Erlang запоминанием

Question

Предположим, у вас есть простая функция, которая может получить довольно дорого для больших значений:

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

Где я могу найти простой пример кэширования (или memoizing) значений функции с помощью dets?

Любые другие способы упрощения запоминания будут высоко оценены.

Answer 1

Идея заключается в том, что каждый раз, когда вы запрашиваете у вас тяжелый расчет, вы сразу же проверяете кеш, если вы его уже оценили. Если да, вы просто возвращаете сохраненное значение. Если нет, вы должны оценить новое значение и сохранить его, прежде чем возвращать его конечному пользователю.

A dict, а не таблица dets, также могут работать.

(следующее решение непроверенное)

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

Вы можете инкапсулировать все это в Erlang generic server. В функции init вы должны создать таблицу DETS, функция fact/1 должна представлять ваш API, и вы должны реализовать логику в функциях handle_call.

Приятным примером может быть создание службы сокращения для URL-адресов, кэшированных.

Как было предложено @Zed, имеет смысл хранить частичные результаты, чтобы избежать дальнейших повторных вычислений. Если дело обстоит именно так:

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

Очевидно, что даже если это помогает в больших количествах, вы должны учитывать дополнительные затраты на добавление записи в справочной таблице для каждого шага. Учитывая причины, по которым было введено кэширование (мы предполагаем, что расчет очень тяжелый, поэтому время вставки поиска незначительно), это должно быть совершенно нормально.

Answer 2

В зависимости от вашего дела, вы можете также использовать process dictionary для запоминания:

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.