読者です 読者をやめる 読者になる 読者になる

Erlangでたらい回し

まずは普通に。

-module(tak).
-compile(export_all).

tak( X, Y, Z ) ->
    if X =< Y ->
            Y;
       true ->
            tak(
              tak( X-1, Y, Z ),
              tak( Y-1, Z, X ),
              tak( Z-1, X, Y )
             )
    end.

bench( X, Y, Z ) ->
    { Time, Ans } = timer:tc(?MODULE, tak, [X, Y, Z]),
    io:format("tak(~p, ~p, ~p) = ~p : time ~p msec~n", [X, Y, Z, Ans, Time/1000]).
Eshell V5.5  (abort with ^G)
1> c(tak).
{ok,tak}
2> tak:bench(12, 6, 0).
tak(12, 6, 0) = 12 : time 768.139 msec
ok

memoize 版。dictionary を引き回すところが汚すぎる……

-module(tak).
-compile(export_all).

tak_memoize( X, Y, Z, Dict ) ->
    if X =< Y ->
            { Y, Dict };
       true ->
            case dict:find( { X, Y, Z }, Dict ) of
                { ok, Value } ->
                    { Value, Dict };
                error         ->
                    { X2, DictX }    = tak_memoize( X-1, Y, Z, Dict  ),
                    { Y2, DictY }    = tak_memoize( Y-1, Z, X, DictX ),
                    { Z2, DictZ }    = tak_memoize( Z-1, X, Y, DictY ),
                    { Value, DictV } = tak_memoize( X2, Y2, Z2, DictZ ),
                    { Value, dict:store( { X, Y, Z }, Value, DictV ) }
            end
    end.

bench_memoize( X, Y, Z ) ->
    D = dict:new(),
    { Time, { Ans, _ }} = timer:tc(?MODULE, tak_memoize, [X, Y, Z, D]),
    io:format("tak_memoize(~p, ~p, ~p) = ~p : time ~p msec~n", [X, Y, Z, Ans, Time/1000]).
tak_memoize(12, 6, 0) = 12 : time 0.611000 msec
tak_memoize(100, 50, 0) = 100 : time 73.5050 msec

[追記]
コメントで教えていただきました。

tak( X, Y, Z ) ->
     when X =< Y -> Y;
tak( X, Y, Z ) ->
     tak( tak( X-1, Y, Z ),
          tak( Y-1, Z, X ),
          tak( Z-1, X, Y ) ).

こっちの方がすっきりしていいですね。