[erlang-questions] speeding up 3N+1

[June Kim]

Well, I tried it with ets:

Replace the three cache functions with the following:

newCache()->
    Cache=ets:new(test,[set]),
    ets:insert(Cache,{1,1}),
    Cache.
store(K,V,Cache)->
    ets:insert(Cache,{K,V}),
    Cache.
find(K,Cache)->
    case ets:lookup(Cache,K) of
        [] -> error;
        [{K,V}] -> {ok,V}
    end.

Now max(1,100000) takes about 0.9 secs, and max(1,1000000) takes about 10 secs.

Exploiting the trick in the process dictionary version(when N is odd,
3N+1 is even), for one million, it reduces to about 8 secs.

It's a huge improvement, but still inferior to the process dictionary
version. Moreover, ets isn't functional data structure(with
side-effects).

So the process dictionary is the king?

2007/4/7, June Kim <juneaftn@REDACTED>:
> Hello,
>
> First of all, please keep in mind that I am a newbie in Erlang. (sorry
> if the codes annoy you)
>
> Please have a look at this famous problem. http://acm.uva.es/p/v1/100.html
>
> The input number can be upto 1,000,000. (let's just suppose 1 million
> is included, even though the problem states the maximal input is less
> than 1 million) Let's see the worst case(when the start/end pair is
> {1, 1000000}) time performance of the program.
>
> Following is a trial at solving this problem:
>
> -module(tnp1_process_dict).
> -compile(export_all).
>
> cycle(1) ->
>    1;
> cycle(N) ->
>    case get(N) of
>    undefined ->
>        SN = if
>             N rem 2 =:= 0 ->
>             1 + cycle(N div 2);
>             true ->
>             2 + cycle((3 * N + 1) div 2)
>         end,
>        put(N, SN),
>        SN;
>    Cached ->
>        Cached
>    end.
>
> max(A, B) ->
>    lists:max(lists:map(fun cycle/1, lists:seq(A, B))).
>
> Actually, it's from a friend of mine, who is also in the same Erlang
> community(we are all just novices though) with me. It's quite
> effiecient.
>
> 1> timer:tc(tnp1_process_dict,max,[1,1000000]).
> {2547000,525}
>
> Less than 3 seconds on my sluggish machine. Good.
>
> However, I didn't quite like the solution. It uses the process
> dictionary. From reading Erlang books and manuals, I thought the
> process dictionary should be the last resort for this kind of usage. I
> thought I could deal the problem without using the process dictionary,
> without trading off the speed.
>
> Following is my trial:
>
> -module(tnp1_functional).
> -compile(export_all).
>
> newCache()->
>    dict:from_list([{1,1}]).
> store(K,V,Cache)->
>    dict:store(K,V,Cache).
> find(K,Cache)->
>    dict:find(K,Cache).
>
> nn(N) when N rem 2 =:= 0 ->
>    N div 2;
> nn(N) ->
>    3*N+1.
>
> update([],_,Cache)->
>    Cache;
> update([H|ToStore],V,Cache)->
>    Cache2=store(H,V+1,Cache),
>    update(ToStore,V+1,Cache2).
>
> cl(N,Cnt,Cache,ToStore)->
>    case find(N,Cache) of
>        {ok,V} ->
>            Cache2=update(ToStore,V,Cache),
>            {Cnt+V,Cache2};
>        error  ->
>            cl(nn(N),Cnt+1,Cache,[N|ToStore])
>    end.
>
> maxcl(From,To,Cache,Max) when From>To ->
>     {Max,Cache};
> maxcl(From,To,Cache,Max)->
>    {Cl,Cache2}=cl(From,0,Cache,[]),
>    maxcl(From+1,To,Cache2,lists:max([Cl,Max])).
>
> maxcl(From,To)->
>    Cache=newCache(),
>    maxcl(From,To,Cache,1).
>
> max(From,To)->
>    {V,_}=maxcl(From,To),
>    V.
>
> It's much longer. And much slower; I'd say excruciatingly.
>
> 1> timer:tc(tnp1_functional,max,[1,100000]).
> {7953000,351}
>
> See? It's 100,000, not one million, even. When I ran it with one
> million, it didn't end at least in a couple of minutes.
>
> Maybe my choice of using dict is wrong? Could ets be substantially
> better? Or my approach totally wrong? I don't know yet. (I'll
> experiment with other data structures and approaches, though)
>
> Okay, that's it. I would appreciate any suggestions for improvement.
>
> June
>