Euler#4拥有更大的域名

Question

考虑修改后的欧拉问题#4 - "找到最大回文数,它是100到9999之间两个数的乘积."

rev :: Int -> Int
rev x = rev' x 0

rev' :: Int -> Int -> Int
rev' n r
    | n == 0 = r
    | otherwise = rev' (n `div` 10) (r * 10 + n `mod` 10)

pali :: Int -> Bool
pali x = x == rev x

main :: IO ()
main = print . maximum $ [ x*y | x <- nums, y <- nums, pali (x*y)]
    where
        nums = [9999,9998..100]

• 此Haskell的溶液中使用-O2,并ghc 7.4.1需要大约18秒.
• 类似的C解决方案需要0.1秒.

所以Haskell慢了180倍.我的解决方案有什么问题？我认为Haskell解决的这类问题非常好.

附录 - 模拟C解决方案:

#define A   100
#define B   9999
int ispali(int n)
{
    int n0=n, k=0;
    while (n>0) {
        k = 10*k + n%10;
        n /= 10;
    }
    return n0 == k;
}
int main(void)
{
    int max = 0;
    for (int i=B; i>=A; i--)
        for (int j=B; j>=A; j--) {
            if (i*j > max && ispali(i*j))
                max = i*j;      }
    printf("%d\n", max);
}

Answer 1

类似的C解决方案

这是一种常见的误解.

列表不是循环!

除非编译器能够从代码中删除列表,否则使用列表来模拟循环会产生性能影响.

如果你想比较苹果和苹果,那么写Haskell结构或多或少等同于一个循环,一个尾递归工作者(使用严格的累加器,尽管编译器通常很聪明,可以自己弄清楚严格性).

现在让我们更详细一点.为了比较,用gcc -O3编译的C在这里需要大约0.08秒,用ghc -O2编译的原始Haskell需要~20.3秒,ghc -O2 -fllvm~19.9秒.太可怕了.

原始代码中的一个错误是使用div和mod.C代码使用等效的quot和rem,映射到机器分区指令并且比div和更快mod.对于正面参数,语义是相同的,所以每当你知道参数总是非负的时候,就不要使用div和mod.

更改它,使用本机代码生成器进行编译时运行时间变为~15.4秒,使用LLVM后端进行编译时运行时间变为~2.9秒.

不同之处在于,即使机器分割操作非常慢,LLVM也会通过乘法和移位操作替换除法/余数.对于本机后端手动执行相同操作(实际上,利用我知道参数总是非负的这一事实,稍微更好的替换)将其时间缩短到~2.2秒.

我们越来越近,但仍然与C相去甚远.

这是由于列表.该代码仍构建一个回文列表(并遍历Int两个因素的s 列表).

由于列表不能包含未装箱的元素,这意味着代码中存在大量的装箱和拆箱,这需要时间.

因此,让我们删除列表,并查看将C转换为Haskell的结果:

module Main (main) where

a :: Int
a = 100

b :: Int
b = 9999

ispali :: Int -> Bool
ispali n = go n 0
  where
    go 0 acc = acc == n
    go m acc = go (m `quot` 10) (acc * 10 + (m `rem` 10))

maxpal :: Int
maxpal = go 0 b
  where
    go mx i
        | i < a = mx
        | otherwise = go (inner mx b) (i-1)
          where
            inner m j
                | j < a = m
                | p > m && ispali p = inner p (j-1)
                | otherwise = inner m (j-1)
                  where
                    p = i*j

main :: IO ()
main = print maxpal

嵌套循环被转换为两个嵌套的工作函数,我们使用累加器来存储到目前为止找到的最大回文.使用ghc -O2编译,运行时间约为0.18秒,ghc -O2 -fllvm运行时间约为0.14秒(是的,LLVM优于环路代码生成器优化循环).

仍然不完全存在,但大约2的因素并不算太糟糕.

也许有些人发现以下循环被抽象出来更具可读性,生成的核心用于所有意图和目的相同(模数参数顺序切换),当然性能相同:

module Main (main) where

a :: Int
a = 100

b :: Int
b = 9999

ispali :: Int -> Bool
ispali n = go n 0
  where
    go 0 acc = acc == n
    go m acc = go (m `quot` 10) (acc * 10 + (m `rem` 10))

downto :: Int -> Int -> a -> (a -> Int -> a) -> a
downto high low acc fun = go high acc
  where
    go i acc
        | i < low   = acc
        | otherwise = go (i-1) (fun acc i)

maxpal :: Int
maxpal = downto b a 0 $ \m i ->
            downto b a m $ \mx j ->
                let p = i*j
                in if mx < p && ispali p then p else mx

main :: IO ()
main = print maxpal