如何提高这个Haskell程序的性能?
我正在解决Project Euler中的问题,作为一种学习Haskell的方法,我发现我的程序比同类C版本慢得多,即使在编译时也是如此。 我该怎么做才能加速我的Haskell程序?
例如,我对问题14的powershell解决方案是:
import Data.Int import Data.Ord import Data.List searchTo = 1000000 nextNumber :: Int64 -> Int64 nextNumber n | even n = n `div` 2 | otherwise = 3 * n + 1 sequenceLength :: Int64 -> Int sequenceLength 1 = 1 sequenceLength n = 1 + (sequenceLength next) where next = nextNumber n longestSequence = maximumBy (comparing sequenceLength) [1..searchTo] main = putStrLn $ show $ longestSequence
这需要大约220秒,而“等效”暴力C版本只需要1.2秒。
#include int main(int argc, char **argv) { int longest = 0; int terms = 0; int i; unsigned long j; for (i = 1; i terms) { terms = this_terms; longest = i; } if (j % 2 == 0) j = j / 2; else j = 3 * j + 1; } } printf("%d\n", longest); return 0; }
我究竟做错了什么? 或者我天真地认为Haskell甚至可以接近C的速度?
(我正在使用gcc -O2编译C版本,使用ghc -make -O编译Haskell版本)。
出于测试目的,我刚设置searchTo = 100000
。 所需时间为7.34秒 。 一些修改会带来一些重大改进:
-
使用
Integer
而不是Int64
。 这将时间提高到1.75秒 。 -
使用累加器(你不需要sequenceLength是懒惰的吗?) 1.54s 。
seqLen2 :: Int -> Integer -> Int seqLen2 a 1 = a seqLen2 an = seqLen2 (a+1) (nextNumber n) sequenceLength :: Integer -> Int sequenceLength = seqLen2 1
-
使用
quotRem
重写quotRem
,从而避免计算两次除法(even
一次,div
一次)。 1.27s 。nextNumber :: Integer -> Integer nextNumber n | r == 0 = q | otherwise = 6*q + 4 where (q,r) = quotRem n 2
-
使用Schwartzian变换而不是
maximumBy
。maximumBy . comparing
的问题maximumBy . comparing
maximumBy . comparing
是为每个值调用sequenceLength
函数不止一次。 0.32秒longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]
注意:
- 我通过使用
ghc -O
进行编译来检查时间并使用+RTS -s
运行 - 我的机器在Mac OS X 10.6上运行。 GHC版本是6.12.2。 编译后的文件采用i386架构。)
- C问题在0.078s运行,带有相应的参数。 它是用
gcc -O3 -m32
编译的。
虽然这已经相当陈旧了,但让我说一下,还有一个关键点,以前没有解决过。
首先,我的盒子上的不同程序的时间。 由于我使用的是64位Linux系统,它们显示出一些不同的特性:使用Integer
而不是Int64
并不像32位GHC那样提高性能,其中每个Int64
操作都会产生C调用的成本使用Integer
符合有符号32位整数的计算不需要外部调用(因为这里只有少数操作超出该范围,因此在32位GHC上, Integer
是更好的选择)。
- C:0.3秒
- 原始Haskell:14.24秒,使用
Integer
而不是Int64
:33.96秒 - KennyTM的改进版本:5.55秒,使用
Int
:1.85秒 - Chris Kuklewicz的版本:5.73秒,使用
Int
:1.90秒 - FUZxxl的版本:3.56秒,使用
quotRem
而不是divMod
:1.79秒
那我们有什么?
- 使用累加器计算长度,以便编译器可以(基本上)将其转换为循环
- 不要重新计算比较的序列长度
- 不要使用
div
resp。divMod
什么时候没必要,quot
resp。quotRem
要快得多
什么仍然缺少?
if (j % 2 == 0) j = j / 2; else j = 3 * j + 1;
我使用的任何C编译器都将测试j % 2 == 0
转换为位掩码,并且不使用除法指令。 GHC(尚未)这样做。 因此,测试even n
或计算n `quotRem` 2
是非常昂贵的操作。 用nextNumber
的Integer
版本替换nextNumber
nextNumber :: Integer -> Integer nextNumber n | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2 | otherwise = 3*n+1
将其运行时间减少到3.25秒(注意:对于Integer
, n `quot` 2
比n `shiftR` 1
快,需要12.69秒!)。
在Int
版本中执行相同操作Int
其运行时间减少到0.41秒。 对于Int
s,除以2的位移比quot
操作快一点,将其运行时间减少到0.39秒。
消除列表的构造(也不会出现在C版本中),
module Main (main) where import Data.Bits result :: Int result = findMax 0 0 1 findMax :: Int -> Int -> Int -> Int findMax start len can | can > 1000000 = start | canlen > len = findMax can canlen (can+1) | otherwise = findMax start len (can+1) where canlen = findLen 1 can findLen :: Int -> Int -> Int findLen l 1 = l findLen ln | n .&. 1 == 0 = findLen (l+1) (n `shiftR` 1) | otherwise = findLen (l+1) (3*n+1) main :: IO () main = print result
产生更小的加速,导致0.37秒的运行时间。
因此,与C版本密切对应的Haskell版本不会花费更长的时间,它是~1.3的因子。
好吧,让我们公平一点,在Haskell版本中没有的C版本效率低下,
if (this_terms > terms) { terms = this_terms; longest = i; }
出现在内循环中。 将其从C版本的内环中取出可将其运行时间缩短至0.27秒,使得系数达到1.4。
比较可能是重新计算sequenceLength
太多。 这是我最好的版本:
type I = Integer data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show) searchTo = 1000000 nextNumber :: I -> I nextNumber n = case quotRem n 2 of (n2,0) -> n2 _ -> 3*n+1 sequenceLength :: I -> Int sequenceLength x = count x 1 where count 1 acc = acc count n acc = count (nextNumber n) (succ acc) longestSequence = maximum . map (\i -> P (sequenceLength i) i) $ [1..searchTo] main = putStrLn $ show $ longestSequence
答案和时间比C慢,但它确实使用任意精度整数(通过Integer
类型):
ghc -O2 --make euler14-fgij.hs time ./euler14-fgij P 525 837799 real 0m3.235s user 0m3.184s sys 0m0.015s
Haskell的列表是基于堆的,而你的C代码非常紧张,根本不使用堆。 您需要重构以删除对列表的依赖性。
即使我有点迟了,这是我的,我删除了对列表的依赖,这个解决方案根本不使用堆。
{-# LANGUAGE BangPatterns #-} -- Compiled with ghc -O2 -fvia-C -optc-O3 -Wall euler.hs module Main (main) where searchTo :: Int searchTo = 1000000 nextNumber :: Int -> Int nextNumber n = case n `divMod` 2 of (k,0) -> k _ -> 3*n + 1 sequenceLength :: Int -> Int sequenceLength n = sl 1 n where sl k 1 = k sl kx = sl (k + 1) (nextNumber x) longestSequence :: Int longestSequence = testValues 1 0 0 where testValues number !longest !longestNum | number > searchTo = longestNum | otherwise = testValues (number + 1) longest' longestNum' where nlength = sequenceLength number (longest',longestNum') = if nlength > longest then (nlength,number) else (longest,longestNum) main :: IO () main = print longestSequence
我用ghc -O2 -fvia-C -optc-O3 -Wall euler.hs
编译了这个片段,它在5秒内运行,而开始实现的80个。 它不使用Integer
,但因为我在64位机器上,结果可能会被欺骗。
在这种情况下,编译器可以解包所有Int
,从而产生非常快的代码。 它运行速度比我迄今为止看到的所有其他解决方案都要快,但C仍然更快。