代码之家 › 专栏 › 技术社区 › stusmith

如何提高Haskell程序的性能?

haskell performance c

stusmith · 技术社区 · 14 年前

我正在努力解决这些问题 Project Euler

例如,我的暴力解决方案 Problem 14 是:

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 <stdio.h>

int main(int argc, char **argv)
{
    int longest = 0;
    int terms = 0;
    int i;
    unsigned long j;

    for (i = 1; i <= 1000000; i++)
    {
        j = i;
        int this_terms = 1;

        while (j != 1)
        {
            this_terms++;

            if (this_terms > terms)
            {
                terms = this_terms;
                longest = i;
            }

            if (j % 2 == 0)
                j = j / 2;
            else
                j = 3 * j + 1;
        }
    }

    printf("%d\n", longest);
    return 0;
}

(我用gcc-O2编译C版本,用ghc-make-O编译Haskell版本)。

5 回复 | 直到 10 年前

duplode 6 年前

为了测试,我刚设置了 searchTo = 100000 7.34秒

使用 Integer 而不是 Int64 . 这样可以缩短 1.75秒

使用累加器(你不需要sequenceLength来懒惰,对吧?) 1.54秒

seqLen2 :: Int -> Integer -> Int
seqLen2 a 1 = a
seqLen2 a n = seqLen2 (a+1) (nextNumber n)

sequenceLength :: Integer -> Int
sequenceLength = seqLen2 1

重写 nextNumber 使用 quotRem ,从而避免了计算两次除法(一次在 even 一次又一次 div ). 1.27秒 .

nextNumber :: Integer -> Integer
nextNumber n 
    | r == 0    = q
    | otherwise = 6*q + 4
    where (q,r) = quotRem n 2

使用 Schwartzian transform 而不是 maximumBy . 问题 maximumBy . comparing 那是那个吗 sequenceLength 对每个值调用函数不止一次。 0.32秒
```
longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]
```

我用编译来检查时间 ghc -O 和你一起跑 +RTS -s
我的机器在MacOSX10.6上运行。GHC版本是6.12.2。编译后的文件采用i386体系结构。)
0.078秒 使用相应的参数。它是用 gcc -O3 -m32

duplode 6 年前

尽管这已经很老了,让我插一句,有一个关键的问题以前没有解决过。

首先,我的盒子上不同节目的时间安排。因为我使用的是64位linux系统,所以它们显示出一些不同的特性:使用 Integer 而不是 Int64 不会像32位GHC那样提高性能,其中当使用 整数 在有符号32位整数中拟合s不需要外部调用(因为只有很少的操作超过这个范围, 整数 是32位GHC的最佳选择)。

C:0.3秒
原始Haskell:14.24秒,使用而不是 国际64
KennyTM的改进版本:5.55秒,使用 Int
克里斯·库克列维奇的版本:5.73秒,使用 :1.90秒
FUZxxl版本:3.56秒,使用 quotRem divMod :1.79秒

那我们有什么?

用累加器计算长度,这样编译器就可以把它(基本上)转换成一个循环
不要为比较重新计算序列长度
不要使用 div 负责。 divMod公司 不需要的时候, quot 配额 速度要快得多

if (j % 2 == 0)
    j = j / 2;
else
    j = 3 * j + 1;

我使用过的任何C编译器都会转换测试 j % 2 == 0 变成位掩蔽,不使用除法指令。GHC还没有这样做。So测试 even n n `quotRem` 2 这是一个相当昂贵的手术。更换 nextNumber 在肯尼特家

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

将其运行时间减少到3.25秒(注:对于 , n `quot` 2 比…快 n `shiftR` 1 ,需要12.69秒!)。

同样的事情 内景 版本将其运行时间减少到0.41秒。为了 s、除以2的位移位比 引用

消除列表的构造(在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 l n
    | n .&. 1 == 0  = findLen (l+1) (n `shiftR` 1)
    | otherwise     = findLen (l+1) (3*n+1)

main :: IO ()
main = print result

因此,Haskell版本与C版本非常接近,不会花费太多时间,它是~1.3的一个系数。

好吧,公平地说,C版本中有一个低效的地方,这在Haskell版本中是不存在的,

if (this_terms > terms)
{
    terms = this_terms;
    longest = i;
}

出现在内环中。在C版本中,将其从内环中取出将其运行时间减少到0.27秒,使因子约为1.4。

duplode 6 年前

比较可能正在重新计算 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

Puppy 14 年前

Haskell的列表是基于堆的,而您的C代码非常紧凑,根本不使用堆。您需要重构以移除对列表的依赖。

duplode 6 年前

即使我有点晚了,这是我的,我删除了对列表的依赖,这个解决方案也没有使用堆。

{-# 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 k x = 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 Integer ,但因为我在64位机器上,结果可能会被欺骗。

Int 在这种情况下,会产生非常快的代码。它的运行速度比我见过的所有其他解决方案都快,但C仍然更快。