Erlang memoization的简单示例

Question

假设你有一个简单的函数,对于大值来说可能会非常昂贵:

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

我在哪里可以找到一个使用缓存(或记忆)函数值的简单示例dets？

任何其他方便记忆的方式将受到高度赞赏.

Answer 1

根据您的情况,您还可以使用流程字典进行记忆:

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.

Answer 2

这个想法是，每次您要求进行大量计算时，如果您已经对其进行了评估，则立即检查缓存。如果是，您只需返回存储的值即可。如果不是，您必须评估新值并存储它，然后再将其返回给最终用户。

一个dict而不是 det 表也可以工作。

（以下解决方案未经测试）

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

显然，即使这对大量数据有帮助，您也必须考虑为每一步向查找表添加条目的额外成本。考虑到引入缓存的原因（我们假设计算量非常大，因此查找插入时间可以忽略不计），这应该完全没问题。