試圖找到更快的Erlang項目＃14的解決方案

我試圖爲Project Euler的問題14編寫一個解決方案。我最快的 - 不是下面的 - 跑了58秒左右。我發現使用谷歌最快看上去或多或少是這樣的：試圖找到更快的Erlang項目＃14的解決方案

%% 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不是爲了這樣的東西而編寫的，也可以編寫更好的代碼。有人可能知道我可以嘗試獲得一些速度嗎？

來源

2012-09-26 marcus

雖然有1000000個整數，但沒有必要全部計算爲1。經常出現一些「路徑」。例如，13和80具有最相同的步驟。 – halfelf

@halfelf，代碼中提出的問題是用於記憶的'ets'表，所以「路徑」的相同部分不會計算兩次。 – stemm

Erlang使用任意精度整數，不是嗎？如果有的話，使用本機64位整數類型可能會大大加快速度。還有一點，你在查找表（1168611）中輸入了很多數字'> 1000000'。他們中只有46675人再次擡頭看。只記憶'n <= 1000000'的值可能會更快（但這取決於實施記憶的方式）。可能使用可變數組記憶 - 如果可用的話 - 也是一個勝利（這在Haskell中是一個巨大的勝利）。最後，嘗試使用掩碼和移位而不是'rem 2'和'div 2'來提高速度。 –

我已經加快你的代碼位：指定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-27 01:35:33 stemm

您的版本需要12秒鐘。但我猜是因爲每次調用ets：插入拷貝對象，ets只是在一秒鐘內不需要插入數百萬個插件的時候... – marcus

一般來說，原始的CPU綁定操作並不是Erlang的強項。正如您注意到的那樣，問題是數據被複制到ETS表中或從ETS表複製。中央ETS表還具有鎖定原子更新的優點。因此，如果您願意，您可以輕鬆獲得更多內核來解決問題。儘管如此，你不會接近C++或C解決方案的速度。

你對這類問題的另一個問題是可變性。 Erlang在其（順序）核心中具有（幾乎）純功能語言。所以你不能希望用一個短暫的散列表或者一個數組來存儲它所運行的數百萬個條目，以此勝出C++解決方案。您可以嘗試array模塊，但我懷疑它會更快。

來源

2012-09-29 09:41:03

對我來說問題14是我找不到快速答案的第一個問題遠。所以我更害怕這只是我的錯。（使用我發現的數組的解決方案不是更快btw。） – marcus

試圖找到更快的Erlang項目＃14的解決方案

回答

相關問題