0

我试图为 Project Euler 的问题 14 编写一个解决方案。我最快的——不是下面那个——跑了 58 秒左右。我使用谷歌发现的最快看起来或多或少是这样的：

%% 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++ 中最快的解决方案只需要 0.18 秒，快了 58 倍。所以我想即使 Erlang 不是为这样的东西而生的，也可以编写更好的代码。有人可能知道我可以尝试什么来提高速度吗？

4

2 回答 2

1

我已经加快了您的代码速度：指定 ets as 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}).

在 shell 中测试 - 你的模块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 表中复制出来。中央 ETS 表也有锁定的优势：原子更新。因此，如果您愿意，您可以轻松获得更多核心来解决问题。但是，您不会接近 C++ 或 C 解决方案的速度。

对于此类问题，您遇到的另一个问题是可变性。Erlang 在其（顺序）核心中有（几乎）纯函数式语言。因此，您不能指望用一个临时哈希表或一个数组来击败一个 C++ 解决方案，它可以在其中存储它所操作的数百万个条目。您可以尝试该array模块，但我怀疑它会更快。

于 2012-09-29T09:41:03.300 回答