Простой пример для Erlang memoization
Предположим, что у Вас есть простая функция, которая может стать довольно дорогой для больших значений:
fact(0) -> 1;
fact(N) -> N * fact(N - 1).
Где я могу найти простой пример кэширования (или memoizing) значениями функции при помощи dets?
Любой другой путь к легкому memoization высоко ценился бы.
2 ответа
Идея состоит в том, что каждый раз, когда вы запрашиваете свой тяжелый расчет, вы сразу же проверяете кеш, если вы уже оценили его. Если да, вы просто возвращаете сохраненное значение. Если нет, вы должны оценить новое значение и сохранить его, прежде чем возвращать его конечному пользователю.
Также может работать 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 . В функции 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.
Очевидно, даже если это помогает для больших чисел, вы должны учитывать дополнительные затраты на добавление записи в таблицу поиска на каждом шаге. Учитывая причины, по которым было введено кеширование (мы предполагаем, что расчет очень тяжелый, поэтому время вставки поиска незначительно), это должно быть совершенно нормально.
В зависимости от вашего случая, вы также можете использовать словарь процессов для мемоизации:
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.