我已經(jīng)采取了問題＃12從項目歐拉作為編程鍛煉和比較我的（肯定不是最優(yōu)的）實現(xiàn)在C，Python和Erlang和Haskell的。為了獲得更高的執(zhí)行時間，我搜索的第一個三角形數(shù)的除數(shù)大于1000，而不是原始問題中所述的500。結(jié)果如下：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％我認(rèn)為C具有很大的優(yōu)勢，因為它使用long進(jìn)行計算，而不使用其他任意三個整數(shù)。另外，它不需要先加載運行時（其他是否需要加載？）。問題1： Erlang，Python和Haskell是否會由于使用任意長度的整數(shù)而失去速度，或者只要值小于，它們就不會丟失MAXINT嗎？問題2： 為什么Haskell這么慢？是否有編譯器標(biāo)志可以使您剎車，或者它是我的實現(xiàn)？（后者很有可能是因為Haskell是一本對我有七個印章的書。）問題3： 能否為我提供一些提示，說明如何在不改變因素確定方式的情況下優(yōu)化這些實現(xiàn)？以任何方式進(jìn)行優(yōu)化：對語言更好，更快，更“原生”。編輯：問題4： 我的函數(shù)實現(xiàn)是否允許LCO（最后一次調(diào)用優(yōu)化，又稱為尾部遞歸消除），從而避免在調(diào)用堆棧中添加不必要的幀？盡管我不得不承認(rèn)我的Haskell和Erlang知識非常有限，但我確實嘗試過用四種語言盡可能地實現(xiàn)相同的算法。
3 回答
喵喔喔
TA貢獻(xiàn)1735條經(jīng)驗 獲得超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秒內(nèi)運行（由于顯示-O2標(biāo)記）
您的factorCount'代碼未明確輸入且默認(rèn)為Integer（感謝Daniel在這里糾正了我的誤診?。?。使用給出顯式類型簽名（無論如何都是標(biāo)準(zhǔn)做法）Int，時間更改為11.1秒
在factorCount'你不必要的呼喚fromIntegral。修復(fù)不會導(dǎo)致任何變化（編譯器很聰明，對您來說很幸運）。
您mod在rem更快更充分的地方使用了。這將時間更改為8.5秒。
factorCount'不斷應(yīng)用兩個永不更改的自變量（number，sqrt）。工人/包裝工人的轉(zhuǎn)型為我們提供了：
$ time ./so
842161320
real 0m7.954s
user 0m7.944s
sys 0m0.004s
沒錯，7.95秒。始終比C解決方案快半秒。沒有-fllvm標(biāo)記，我仍然會收到消息8.182 seconds，因此NCG后端在這種情況下也表現(xiàn)良好。
結(jié)論：Haskell很棒。
結(jié)果代碼
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
編輯：現(xiàn)在我們已經(jīng)探索了，讓我們解決問題
問題1：erlang，python和haskell是否會由于使用任意長度的整數(shù)而失去速度，還是只要它們的值小于MAXINT，它們就不會丟失嗎？
在Haskell中，使用Integer速度慢于Int但要慢多少，取決于執(zhí)行的計算。幸運的是（對于64位計算機）Int就足夠了。出于可移植性考慮，您可能應(yīng)該重寫我的代碼以使用Int64或Word64（C不是唯一帶有的語言long）。
問題2：為什么haskell這么慢？是否有編譯器標(biāo)志可以使您剎車，或者它是我的實現(xiàn)？（后者很可能因為haskell是一本對我有七個印章的書。）
問題3：能否為我提供一些提示，說明如何在不改變因素確定方式的情況下優(yōu)化這些實現(xiàn)？以任何方式進(jìn)行優(yōu)化：對語言更好，更快，更“原生”。
這就是我上面回答的。答案是
0）通過使用優(yōu)化 -O2
1）盡可能使用快速（特別是：不可裝箱）類型
2）rem不是mod（經(jīng)常被遺忘的優(yōu)化），并且
3）worker / wrapper轉(zhuǎn)換（也許是最常見的優(yōu)化）。
問題4：我的功能實現(xiàn)是否允許LCO，從而避免在調(diào)用堆棧中添加不必要的幀？
是的，這不是問題。做得好，很高興您考慮了這一點。
陪伴而非守候
TA貢獻(xiàn)1757條經(jīng)驗 獲得超8個贊
Erlang實現(xiàn)存在一些問題。作為以下內(nèi)容的基準(zhǔn)，我測得的未經(jīng)修改的Erlang程序的執(zhí)行時間為47.6秒，而C代碼為12.7秒。
如果要運行計算密集型的Erlang代碼，您應(yīng)該做的第一件事就是使用本機代碼。使用進(jìn)行編譯，erlc +native euler12時間縮短至41.3秒。但是，這比這種代碼的本機編譯要低得多（僅15％），問題是您使用-compile(export_all)。這對于實驗很有用，但是所有功能都可以從外部訪問的事實導(dǎo)致本機編譯器非常保守。（普通的BEAM仿真器不會受到太大影響。）用替換該聲明可以-export([solve/0]).提供更好的加速：31.5秒（比基線快將近35％）。
但是代碼本身有一個問題：對于factorCount循環(huán)中的每個迭代，您都可以執(zhí)行以下測試：
factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count + 1;
C代碼不會執(zhí)行此操作。通常，在同一代碼的不同實現(xiàn)之間進(jìn)行公平的比較可能比較棘手，特別是如果算法是數(shù)字的，因為您需要確保它們實際上在做相同的事情。盡管某個實現(xiàn)最終會達(dá)到相同的結(jié)果，但由于某個地方的某些類型轉(zhuǎn)換而導(dǎo)致的一種實現(xiàn)中的輕微舍入錯誤可能會導(dǎo)致其執(zhí)行的迭代次數(shù)要多于另一個實現(xiàn)。
為了消除這種可能的錯誤源（并消除每次迭代中的額外測試），我重新編寫了factorCount函數(shù)，如下所示，該函數(shù)非常類似于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根本不適合編寫數(shù)字代碼，在這樣的程序上，它僅比C慢50％。
最后，關(guān)于您的問題：
問題1：erlang，python和haskell是否由于使用任意長度的整數(shù)而導(dǎo)致速度變慢，或者只要值小于MAXINT，它們是否會變慢？
是的，有點。在Erlang中，沒有辦法說“結(jié)合使用32/64位算術(shù)”，因此，除非編譯器可以證明整數(shù)的某些界限（通常不能這樣做），否則它必須檢查所有計算以查看是否可以將它們放入單個標(biāo)記的單詞中，或者是否必須將它們轉(zhuǎn)換為堆分配的bignum。即使在運行時實際上沒有使用大數(shù)，也必須執(zhí)行這些檢查。另一方面，這意味著您知道，如果您突然給它比以前更大的輸入，該算法將永遠(yuǎn)不會因為意外的整數(shù)環(huán)繞而失敗。
問題4：我的功能實現(xiàn)是否允許LCO，從而避免在調(diào)用堆棧中添加不必要的幀？
是的，您的Erlang代碼在上次通話優(yōu)化方面是正確的。
添加回答
舉報
0/150
提交
取消