[erlang-questions] speeding up 3N+1

[June Kim]

2007/4/7, Vance Shipley <vances@REDACTED>:
> On Sat, Apr 07, 2007 at 10:18:59PM +0900, June Kim wrote:
> }  Please have a look at this famous problem. http://acm.uva.es/p/v1/100.html
>
> June,
>
> In functional programming you pass arguments instead of using
> global variables.
>
> -module(threeNplus1).
> -export([do/1]).
>
> do(1) ->
>        io:fwrite(" 1~n");
> do(N) when N rem 2 /= 0 ->
>        io:fwrite(" ~b", [N]),
>        do(3 * N + 1);
> do(N) ->
>        io:fwrite(" ~b", [N]),
>        do(N div 2).
>
> 1> threeNplus1:do(22).
>  22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
> ok
>
> }  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.
>
> The really big problem above is in tail recursion.  You don't
> want to have to wait for the answer to cycle(N div 2) before
> knowing the answer to cycle(N).
>
>        -Vance
>
>

Yes. I am well aware of those issues. (the code isn't mine, but from a
friend of mine who's into functional programming for the first time
with Erlang -- I have programmed in other FP languages before)

His code uses global variable(process dictionary) and not
tail-recursive. However, it's the fastest. (even in a "functional
programming" language -- ironic, isn't it?)

My version using dict, which is also included in my original posting(I
don't think you have seen it yet), is tail-recursive and functional,
but slow.

I did some experimentations.

%%<data structure> <time(sec) for upto 10^5>/<time for upto 10^6>

%%dict 7s/?s

newCache()->
   dict:from_list([{1,1}]).
store(K,V,Cache)->
   dict:store(K,V,Cache).
find(K,Cache)->
   dict:find(K,Cache).




%%ets/set 0.1s/10s

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.


%%gb_trees 2.6s/32s
newCache()->
   T1=gb_trees:empty(),
   gb_trees:enter(1,1,T1).
store(K,V,Cache)->
   gb_trees:enter(K,V,Cache).
find(K,Cache)->
   case gb_trees:lookup(K,Cache) of
       none -> error;
       {value,V} -> {ok,V}
   end.


%%process dict 0.4s/5s
newCache()->
   erase(),
   put(1,1),
   cache.
store(K,V,_Cache)->
   put(K,V),
   cache.
find(K,_Cache)->
   case get(K) of
       undefined -> error;
       V -> {ok,V}
   end.

Could you help me improving the speed of these codes with FP approach?