如何提高这个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秒 。 一些修改会带来一些重大改进:

  1. 使用Integer而不是Int64 。 这将时间提高到1.75秒

  2. 使用累加器(你不需要sequenceLength是懒惰的吗?) 1.54s

     seqLen2 :: Int -> Integer -> Int seqLen2 a 1 = a seqLen2 an = seqLen2 (a+1) (nextNumber n) sequenceLength :: Integer -> Int sequenceLength = seqLen2 1 
  3. 使用quotRem重写quotRem ,从而避免计算两次除法( even一次, div一次)。 1.27s

     nextNumber :: Integer -> Integer nextNumber n | r == 0 = q | otherwise = 6*q + 4 where (q,r) = quotRem n 2 
  4. 使用Schwartzian变换而不是maximumBymaximumBy . 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秒

那我们有什么?

  1. 使用累加器计算长度,以便编译器可以(基本上)将其转换为循环
  2. 不要重新计算比较的序列长度
  3. 不要使用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是非常昂贵的操作。 用nextNumberInteger版本替换nextNumber

 nextNumber :: Integer -> Integer nextNumber n | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2 | otherwise = 3*n+1 

将其运行时间减少到3.25秒(注意:对于Integern `quot` 2n `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仍然更快。