memoise

erlangでメモ化(2005/09/03/Erlang/fixedpointの続き)。

http://www.kmonos.net/wlog/52.php#_0212050903

Processを使ったメモ化、がんばって作ったよ（`・ω・´）

$ cat memo_fib.erl
-module(memo_fib).
-export([lookup/2, append/3, memoisep/1, memoise/2, memo_fib/1, make_fib/0, test_fib/0]).

lookup (N, MM) ->
    case lists:keysearch(N, 1, MM) of
        {value, {_, T}} ->
            {value, T};
       false -> false
    end.

append (N, M, MM) ->
    lists:keymerge(1, [{N, M}], MM).

memoisep (MM) ->
    receive
        % debug
        {show} ->
            io:fwrite("~w~n", [MM]),
            NMM = MM;
        {lookup, P, N} ->
            case lookup(N, MM) of
                {value, T} ->
                    P ! {value, T};
                false ->
                    P ! false
            end,
            NMM = MM;
        {append, P, N, M} ->
            NMM = append(N, M, MM),
            P ! NMM
    end,
    memoisep(NMM).

memoise (P, F) ->
    fun (N) ->
            P ! {lookup, self(), N},
            receive
                {value, T} ->
                    % debug
                    % io:fwrite("cache hit ~w is ~w~n", [N, T]);
                    true; % dummy for nodebug
                false ->
                    T = F(N),
                    P ! {append, self(), N, T}
            end,
            T
    end.

memo_fib (P) ->
    memoise(P, fun (X) ->
                       if X =< 1 -> 1;
                          true   -> (memo_fib(P))(X - 1) + (memo_fib(P))(X - 2)
                       end
               end).

make_fib () ->
    P = spawn(memo_fib, memoisep, [[]]),
    fun (N) ->
            (memo_fib(P))(N)
    end.

test_fib () ->
    Fib = memo_fib:make_fib(),
    io:fwrite("Fib(1000) is ~w~n", [Fib(1000)]),
    halt().

$ erl
1> c(memo_fib).
{ok,memo_fib}
2> Fib = memo_fib:make_fib().
#Fun<memo_fib.x.xxxxxxxxx>
3> lists:map(Fib, [1, 2, 3, 4, 5]).
[1,2,3,5,8]

process以外のところはSICP Exercise 3.27を参考に書いたので、比較するとおもしろいかも。

とりあえずベンチマーク。

$ time erl -noshell -s memo_fib test_fib
Fib(1000) is 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
erl -noshell -s memo_fib test_fib  0.78s user 0.23s system 93% cpu 1.082 total

1秒程度で返ってくるけど、答えあってる？ Fib(1500)以上はちょっとつらい。メモリが足りない。 Fib(1)...Fib(N)のすべて(しかもNが十分に大きいとBigNumになってしまう)をキャッシュしてるわけだから、あたりまえか。

memo_fib/1と2005/09/03/Erlang/fixedpointのfib_maker/1の違いが、今回のお話のキモなのかなあ(未だにわかってない人)。

ちょっとコードが長すぎるかなあ。もっと短かくなるんだろうなあ。じゃないと、

現場からの報告は、「科学的な」研究よりは精度が劣らざるを得ないが、意味のあるものである可能性は高い。例えばEricssonでUlf Wigerがやった研究では、 ErlangはC++より4〜10倍簡潔で、それに比例して速く開発ができたと結論づけている：
Ericsson内部の開発プロジェクト間の比較によれば、ソフトウェア開発の全ての段階において使用言語(Erlang, PLEX, C, C++, Java)の如何にかかわらず、時間当たりの開発行数は似たような数値となった。言語間の差が出たのはソースコードの量だった。
簡潔さは力なり---Succinctness is Power---

は嘘になってしまうもんな。

それにしても、これは疲れた。慣れないことはすべきじゃないよね。