0

Project Eulerの問題14の解決策を書いてみました。私の最速（以下のものではありません）は、58秒ほどで実行されました。Google を使用して見つけた最速のものは、多かれ少なかれ次のように見えました。

%% ets:delete(collatz) (from shell) deletes the table.

-module(euler) .
-export([problem_14/1]) .

collatz(X) ->
  case ets:lookup(collatz, X) of
    [{X, Val}] -> Val ;
    []         -> case X rem 2 == 0 of
                    true  ->
                      ets:insert(collatz, {X, Val = 1+collatz(X div 2)} ) ,
                      Val ;
                    false ->
                      ets:insert(collatz, {X, Val = 1+collatz(3*X+1)} ) ,
                      Val
                  end
  end .

%% takes 10 seconds for N=1000000 on my netbook after "ets:delete(collatz)".
problem_14(N) ->
  case ets:info(collatz) of
    undefined ->
      ets:new(collatz, [public, named_table]) ,
      ets:insert(collatz,{1,1}) ;
    _         -> ok
  end ,
  lists:max([ {collatz(X), X} || X <- lists:seq(1,N) ]) .

ただし、空のテーブルでは 10.5 秒かかります。私が見つけた C++ での最速のソリューションは、58 倍速い 0.18 秒しかかかりません。したがって、Erlang がそのようなもののために作られていない場合でも、より良いコードを書くことができると思います。速度を上げるために私が何を試みることができるか誰かがおそらく知っていますか?

4

2 に答える 2

1

私はあなたのコードを少しスピードアップしました: ets を として指定し、すべての結果をリストに収集する代わりにordered_setビット演算を使用し、末尾再帰関数を実装しました。max_size_index

-module(collatz).
-compile(export_all).

size(1, _) ->
        1;
size(N, Hashset) ->
        case ets:lookup(Hashset, N) of
                [{N, Size}] ->
                        Size;
                [] ->
                        Size  = 1 + size( next(N), Hashset ),
                        ets:insert(Hashset, {N, Size}),
                        Size
        end.

next(N) when N band 1 == 0 ->
        N bsr 1;
next(N) ->
        (N bsl 1)+N+1.

max_size_index(1, _Hashset, {Index, MaxSize}) ->
        {Index, MaxSize};
max_size_index(N, Hashset, {Index, MaxSize}) ->
        CurrSize = size(N, Hashset),
        case CurrSize > MaxSize of
                true ->
                        max_size_index(N-1, Hashset, {N, CurrSize});
                false ->
                        max_size_index(N-1, Hashset, {Index, MaxSize})
        end.

problem_14(N) ->
        Hashset = ets:new(collatz_count, [public, ordered_set]),
        max_size_index(N, Hashset, {1,1}).

シェルでテスト - あなたのモジュールeulerと私のモジュールcollatz()

1> c(euler).
{ok,euler}
2> 
2> timer:tc(euler, problem_14, [1000000]). 
{4039838,{525,837799}}
3> 
3> c(collatz).
{ok,collatz}
4> 
4> timer:tc(collatz, problem_14, [1000000]). 
{2824109,{837799,525}}

スピードアップの最後のヒント - 大きな間隔をより小さな間隔に分割し、各小さな間隔の計算を並行して (他のノードで) 生成できます。

于 2012-09-27T01:35:33.823 に答える
0

一般に、生の CPU バウンド操作は Erlang の強みではありません。お気づきのように、問題はデータが ETS テーブルとの間でコピーされることです。ロックも行う中央の ETS テーブルには、アトミックな更新という利点があります。したがって、必要に応じて、問題に取り組むためにより多くのコアを簡単に入手できます。ただし、C++ または C ソリューションの速度には近づきません。

この種の問題で発生するもう 1 つの問題は、可変性です。Erlang の (シーケンシャル) コアには (ほぼ) 純粋な関数型言語があります。したがって、エフェメラル ハッシュ テーブルや、操作対象の数百万のエントリを格納できる配列を使用する C++ ソリューションを打ち負かすことは期待できません。モジュールを試すこともできarrayますが、これ以上高速になるとは思えません。

于 2012-09-29T09:41:03.300 に答える