我已經采取了問題＃12從項目歐拉作為編程鍛煉和比較我的（肯定不是最優的）實現在C，Python和Erlang和Haskell的。為了獲得更高的執行時間，我搜索的第一個三角形數的除數大于1000，而不是原始問題中所述的500。結果如下：C：lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.clorenzo@enzo:~/erlang$ time ./euler12.bin842161320real 0m11.074suser 0m11.070ssys 0m0.000s蟒蛇：lorenzo@enzo:~/erlang$ time ./euler12.py 842161320real 1m16.632suser 1m16.370ssys 0m0.250s帶有PyPy的Python：lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 842161320real 0m13.082suser 0m13.050ssys 0m0.020sErlang：lorenzo@enzo:~/erlang$ erlc euler12.erl lorenzo@enzo:~/erlang$ time erl -s euler12 solveErlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]Eshell V5.7.4 (abort with ^G)1> 842161320real 0m48.259suser 0m48.070ssys 0m0.020sHaskell：lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx[1 of 1] Compiling Main ( euler12.hs, euler12.o )Linking euler12.hsx ...lorenzo@enzo:~/erlang$ time ./euler12.hsx 842161320real 2m37.326suser 2m37.240ssys 0m0.080s摘要：C：100％Python：692％（使用PyPy時為118％）Erlang：436％（135％感謝RichardC）哈斯克爾：1421％我認為C具有很大的優勢，因為它使用long進行計算，而不使用其他任意三個整數。另外，它不需要先加載運行時（其他是否需要加載？）。問題1： Erlang，Python和Haskell是否會由于使用任意長度的整數而失去速度，或者只要值小于，它們就不會丟失MAXINT嗎？問題2： 為什么Haskell這么慢？是否有編譯器標志可以使您剎車，或者它是我的實現？（后者很有可能是因為Haskell是一本對我有七個印章的書。）問題3： 能否為我提供一些提示，說明如何在不改變因素確定方式的情況下優化這些實現？以任何方式進行優化：對語言更好，更快，更“原生”。編輯：問題4： 我的函數實現是否允許LCO（最后一次調用優化，又稱為尾部遞歸消除），從而避免在調用堆棧中添加不必要的幀？盡管我不得不承認我的Haskell和Erlang知識非常有限，但我確實嘗試過用四種語言盡可能地實現相同的算法。
3 回答
喵喔喔
TA貢獻1735條經驗 獲得超5個贊
使用GHC 7.0.3，gcc 4.4.6，Linux 2.6.29一個x86_64的Core2雙核（2.5GHz的）機器上，編譯使用ghc -O2 -fllvm -fforce-recomp用于Haskell和gcc -O3 -lm為C.
您的C例程運行8.4秒（比您的運行速度快，原因可能是-O3）
Haskell解決方案可在36秒內運行（由于顯示-O2標記）
您的factorCount'代碼未明確輸入且默認為Integer（感謝Daniel在這里糾正了我的誤診?。Ｊ褂媒o出顯式類型簽名（無論如何都是標準做法）Int，時間更改為11.1秒
在factorCount'你不必要的呼喚fromIntegral。修復不會導致任何變化（編譯器很聰明，對您來說很幸運）。
您mod在rem更快更充分的地方使用了。這將時間更改為8.5秒。
factorCount'不斷應用兩個永不更改的自變量（number，sqrt）。工人/包裝工人的轉型為我們提供了：
$ time ./so
842161320
real 0m7.954s
user 0m7.944s
sys 0m0.004s
沒錯，7.95秒。始終比C解決方案快半秒。沒有-fllvm標記，我仍然會收到消息8.182 seconds，因此NCG后端在這種情況下也表現良好。
結論：Haskell很棒。
結果代碼
factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
where square = sqrt $ fromIntegral number
isquare = floor square
factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
where
go candidate count
| candidate > sqrt = count
| number `rem` candidate == 0 = go (candidate + 1) (count + 2)
| otherwise = go (candidate + 1) count
nextTriangle index triangle
| factorCount triangle > 1000 = triangle
| otherwise = nextTriangle (index + 1) (triangle + index + 1)
main = print $ nextTriangle 1 1
編輯：現在我們已經探索了，讓我們解決問題
問題1：erlang，python和haskell是否會由于使用任意長度的整數而失去速度，還是只要它們的值小于MAXINT，它們就不會丟失嗎？
在Haskell中，使用Integer速度慢于Int但要慢多少，取決于執行的計算。幸運的是（對于64位計算機）Int就足夠了。出于可移植性考慮，您可能應該重寫我的代碼以使用Int64或Word64（C不是唯一帶有的語言long）。
問題2：為什么haskell這么慢？是否有編譯器標志可以使您剎車，或者它是我的實現？（后者很可能因為haskell是一本對我有七個印章的書。）
問題3：能否為我提供一些提示，說明如何在不改變因素確定方式的情況下優化這些實現？以任何方式進行優化：對語言更好，更快，更“原生”。
這就是我上面回答的。答案是
0）通過使用優化 -O2
1）盡可能使用快速（特別是：不可裝箱）類型
2）rem不是mod（經常被遺忘的優化），并且
3）worker / wrapper轉換（也許是最常見的優化）。
問題4：我的功能實現是否允許LCO，從而避免在調用堆棧中添加不必要的幀？
是的，這不是問題。做得好，很高興您考慮了這一點。
陪伴而非守候
TA貢獻1757條經驗 獲得超8個贊
Erlang實現存在一些問題。作為以下內容的基準，我測得的未經修改的Erlang程序的執行時間為47.6秒，而C代碼為12.7秒。
如果要運行計算密集型的Erlang代碼，您應該做的第一件事就是使用本機代碼。使用進行編譯，erlc +native euler12時間縮短至41.3秒。但是，這比這種代碼的本機編譯要低得多（僅15％），問題是您使用-compile(export_all)。這對于實驗很有用，但是所有功能都可以從外部訪問的事實導致本機編譯器非常保守。（普通的BEAM仿真器不會受到太大影響。）用替換該聲明可以-export([solve/0]).提供更好的加速：31.5秒（比基線快將近35％）。
但是代碼本身有一個問題：對于factorCount循環中的每個迭代，您都可以執行以下測試：
factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;
C代碼不會執行此操作。通常，在同一代碼的不同實現之間進行公平的比較可能比較棘手，特別是如果算法是數字的，因為您需要確保它們實際上在做相同的事情。盡管某個實現最終會達到相同的結果，但由于某個地方的某些類型轉換而導致的一種實現中的輕微舍入錯誤可能會導致其執行的迭代次數要多于另一個實現。
為了消除這種可能的錯誤源（并消除每次迭代中的額外測試），我重新編寫了factorCount函數，如下所示，該函數非常類似于C代碼：
factorCount (N) ->
Sqrt = math:sqrt (N),
ISqrt = trunc(Sqrt),
if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
true -> factorCount (N, ISqrt, 1, 0)
end.
factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
case N rem Candidate of
0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
_ -> factorCount (N, ISqrt, Candidate + 1, Count)
end.
此重寫（no export_all）和本機編譯為我提供了以下運行時間：
$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320
real 0m19.468s
user 0m19.450s
sys 0m0.010s
與C代碼相比，還算不錯：
$ time ./a.out
842161320
real 0m12.755s
user 0m12.730s
sys 0m0.020s
考慮到Erlang根本不適合編寫數字代碼，在這樣的程序上，它僅比C慢50％。
最后，關于您的問題：
問題1：erlang，python和haskell是否由于使用任意長度的整數而導致速度變慢，或者只要值小于MAXINT，它們是否會變慢？
是的，有點。在Erlang中，沒有辦法說“結合使用32/64位算術”，因此，除非編譯器可以證明整數的某些界限（通常不能這樣做），否則它必須檢查所有計算以查看是否可以將它們放入單個標記的單詞中，或者是否必須將它們轉換為堆分配的bignum。即使在運行時實際上沒有使用大數，也必須執行這些檢查。另一方面，這意味著您知道，如果您突然給它比以前更大的輸入，該算法將永遠不會因為意外的整數環繞而失敗。
問題4：我的功能實現是否允許LCO，從而避免在調用堆棧中添加不必要的幀？
是的，您的Erlang代碼在上次通話優化方面是正確的。
添加回答
舉報
0/150
提交
取消