archives/2005/09/04

Erlang/Note:memoise

うむ。N=1000程度でスローダウンするのはやっぱりおかしい。

Scheme版

(define (memoise f)
  (let ((m '()))
    (lambda (x)
      (cond ((assoc x m) => cdr)
            (else
             (let ((n (f x)))
               (set! m (cons (cons x n) m))
               n))))))

(define (fib x)
  (if (<= x 1)
      1
      (+ (fib (- x 1)) (fib (- x 2)))))

(set! fib (memoise fib))

GaucheやscmだとN=10000でも大丈夫だし。どこかおかしいに違いない。

と思ったらN=10000時にScheme 48がheap overflowで死亡。 N=8000くらいならなんとか。

うーむ。

Comments

Erlang/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---

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

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

Comments

Audio/g-town-church-sampling-project

G-Town Church Sampling Projectなるプロジェクトがあるらしい。

なんというか、えらいことになってる。

10M超のサウンドフォントがドカスカアップロード中。しかも全部Creative Commons Sampling Plus 1.0 license。

さっそくダウンロードしてみるべ。

Comments