haskell - 具有更大域的 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

The similar C solution

这是一个普遍的误解。
列表不是循环!
除非编译器能够从代码中消除列表，否则使用列表来模拟循环会影响性能。
如果你想比较苹果和苹果，编写 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 .
改变这一点，使用 native 代码生成器编译时，运行时间变为 ~15.4 秒，而使用 LLVM 后端编译时，运行时间变为 ~2.9 秒。
不同之处在于，即使是机器除法运算也很慢，LLVM 用乘法和移位运算代替了除法/余数。为本地后端手动做同样的事情(实际上，利用我知道参数总是非负的事实，一个稍微好一点的替代品)将其时间缩短到约 2.2 秒。
我们越来越近了，但离 C 还差得很远。
那是由于列表。该代码仍然构建一个回文列表(并遍历 Int 的两个因素的列表)。
由于列表不能包含未装箱的元素，这意味着代码中有很多装箱和拆箱，这需要时间。
因此，让我们消除列表，看看将 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 比 native 代码生成器更擅长优化循环)。
仍然不完全在那里，但大约 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