我已经编写了代码欧拉计划的挑战 14, 同时Haskell and C++(ideone 链接)。他们都记得之前在数组中进行的任何计算。
Using ghc -O2
and g++ -O3
C++ 的运行速度分别比 Haskell 版本快 10-15 倍。
虽然我知道 Haskell 版本可能运行得更慢,并且 Haskell 是一种更好编写的语言,但如果知道我可以对 Haskell 版本进行一些代码更改以使其运行得更快(理想情况下在 2 或 2 倍以内),那就太好了C++ 版本的 3)?
哈斯克尔代码在这里:
import Data.Array
import Data.Word
import Data.List
collatz_array =
let
upperbound = 1000000
a = array (1, upperbound) [(i :: Word64, f i :: Int) | i <- [1..upperbound]]
f i = i `seq`
let
check_f i = i `seq` if i <= upperbound then a ! i else f i
in
if (i == 1) then 0 else (check_f ((if (even i) then i else 3 * i + 1) `div` 2)) + 1
in a
main =
putStrLn $ show $
foldl1' (\(x1,x2) (y1,y2) -> if (x2 >= y2) then (x1, x2) else (y1, y2)) $! (assocs collatz_array)
Edit:
我现在还使用未装箱的可变数组完成了一个版本。它仍然比 C++ 版本慢 5 倍,但已经有了显着的改进。代码在ideone上here.
我想知道可变数组版本的改进,使其更接近 C++ 版本。
您的(可变数组)代码存在一些问题:
- 您使用折叠来查找最大链长度,因为数组必须转换为关联列表,这需要 C++ 版本不需要的时间和分配。
- You use
even
and div
用于测试 resp 除以 2。这些都很慢。 g++ 将这两个操作优化为更快的位操作(至少在据说更快的平台上),但 GHC 还没有执行这些低级优化,因此目前,它们必须手动完成。
- You use
readArray
and writeArray
。 C++ 代码中未完成的额外边界检查也需要时间,一旦处理了其他问题,这相当于运行时间的很大一部分(在我的机器上大约为 25%),因为已经完成了算法中有大量的读取和写入。
将其纳入实施中,我得到
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Data.Bits
collatz_array :: ST s (STUArray s Int Int)
collatz_array = do
let upper = 10000000
arr <- newArray (0,upper) 0
unsafeWrite arr 2 1
let check i
| upper < i = return arr
| i .&. 1 == 0 = do
l <- unsafeRead arr (i `shiftR` 1)
unsafeWrite arr i (l+1)
check (i+1)
| otherwise = do
let j = (3*i+1) `shiftR` 1
find k l
| upper < k = find (next k) $! l+1
| k < i = do
m <- unsafeRead arr k
return (m+l)
| otherwise = do
m <- unsafeRead arr k
if m == 0
then do
n <- find (next k) 1
unsafeWrite arr k n
return (n+l)
else return (m+l)
where
next h
| h .&. 1 == 0 = h `shiftR` 1
| otherwise = (3*h+1) `shiftR` 1
l <- find j 1
unsafeWrite arr i l
check (i+1)
check 3
collatz_max :: ST s (Int,Int)
collatz_max = do
car <- collatz_array
(_,upper) <- getBounds car
let find w m i
| upper < i = return (w,m)
| otherwise = do
l <- unsafeRead car i
if m < l
then find i l (i+1)
else find w m (i+1)
find 1 0 2
main :: IO ()
main = print (runST collatz_max)
以及时间(均为 1000 万):
$ time ./cccoll
8400511 429
real 0m0.210s
user 0m0.200s
sys 0m0.009s
$ time ./stcoll
(8400511,429)
real 0m0.341s
user 0m0.307s
sys 0m0.033s
看起来还不错。
重要的提示:该代码仅适用于 64 位 GHC(因此,特别是在 Windows 上,您需要 ghc-7.6.1 或更高版本,以前的 GHC 即使在 64 位 Windows 上也是 32 位),因为中间链元素超过 32 位范围。在 32 位系统上,必须使用Integer
或 64 位整数类型 (Int64
or Word64
)用于跟踪链,但性能成本极高,因为原始 64 位操作(算术和移位)是作为对 32 位 GHC 中 C 函数的外部调用来实现的(fast外部调用,但仍然比直接机器操作慢得多)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)