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);
}

score 9 · Accepted Answer

类似的C解决方案

这是一个普遍的误解。

列表不是循环！

除非编译器能够从代码中消除列表，否则使用列表来模拟循环会影响性能。

如果你想比较苹果和苹果，编写 Haskell 结构或多或少相当于一个循环，一个尾递归工作程序（使用严格累加器，尽管编译器通常足够聪明，可以自己找出严格性）。

现在让我们更详细地看一下。相比之下，使用 gcc -O3 编译的 C 在这里需要 ~0.08 秒，使用 ghc -O2 编译的原始 Haskell 需要 ~20.3 秒，使用 ghc -O2 -fllvm ~19.9 秒。相当可怕。

原始代码中的一个错误是使用divand mod。quotC 代码使用and的等价物rem，它映射到机器除法指令并且比divand更快mod。对于正参数，语义是相同的，所以当你知道参数总是非负时，永远不要使用divand 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

score 2 · Accepted Answer

@axblount 至少部分正确；以下修改使程序运行速度几乎是原来的三倍：

maxPalindrome = foldl f 0
  where f a x | x > a && pali x = x
              | otherwise       = a

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

不过，这仍然会导致 60 倍的减速。

score 1 · Accepted Answer

~~Haskell 可能正在存储整个列表 [ x*y | x <- nums, y <- nums, pali (x*y)] 其中 C 解决方案即时计算最大值。我不确定。~~

此外，如果产品超过之前的最大值，C 解决方案只会计算 ispali。我敢打赌，无论 x*y 是否是可能的最大值，Haskell 计算的都是回文乘积。

score 1 · Accepted Answer

这更符合 C 代码正在做的事情：

maxpali :: [Int] -> Int
maxpali xs = go xs 0
  where
    go [] m     = m
    go (x:xs) m = if x > m && pali(x) then go xs x else go xs m

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

在我的盒子上，这需要 2 秒，而 C 版本需要 0.5 秒。

score 0 · Accepted Answer

在我看来，您遇到了分支预测问题。在 C 代码中，您有两个嵌套循环，一旦在内循环中看到回文，内循环的其余部分就会被快速跳过。

您提供此产品列表而不是嵌套循环的方式我不确定 ghc 是否正在执行任何此预测。

score 0 · Accepted Answer

另一种写法是使用两个折叠，而不是扁平列表上的一个折叠：

-- foldl g0 0 [x*y | x<-[b-1,b-2..a], y<-[b-1,b-2..a], pali(x*y)]      (A)
-- foldl g1 0 [x*y | x<-[b-1,b-2..a], y<-[b-1,b-2..a]]                 (B)
-- foldl g2 0 [ [x*y | y<-[b-1,b-2..a]] | x<-[b-1,b-2..a]]             (C)

maxpal b a = foldl f1 0 [b-1,b-2..a]                              --   (D)
  where
    f1 m x = foldl f2 m [b-1,b-2..a]
      where
        f2 m y | p>m && pali p = p
               | otherwise     = m  
           where p = x*y

main = print $ maxpal 10000 100

似乎运行速度也比(B)（如 larsmans 的回答）快得多（仅比以下基于循环的代码慢 3 倍 - 4 倍）。融合foldl和enumFromThenTo定义为我们提供了“功能循环”代码（如 DanielFischer 的回答），

maxpal_loops b a = f (b-1) 0                                      --   (E)
  where               
    f x m | x < a     = m 
          | otherwise = g (b-1) m 
      where
        g y m | y < a         = f (x-1) m
              | p>m && pali p = g (y-1) p 
              | otherwise     = g (y-1) m
           where p = x*y

该(C)变体非常暗示进一步的算法改进（当然，这超出了原始 Q 的范围），利用列表中的隐藏顺序，被扁平化破坏：

{- foldl g2 0 [ [x*y | y<-[b-1,b-2..a]] | x<-[b-1,b-2..a]]             (C)
   foldl g2 0 [ [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]]             (C1)
   foldl g0 0 [ safehead 0 . filter pali $
                [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]]             (C2)
   fst $ until ... (\(m,s)-> (max m .
                safehead 0 . filter pali . takeWhile (> m) $
                                                   head s, tail s))          
           (0,[ [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]])            (C3)
   safehead 0 $ filter pali $ mergeAllDescending
              [ [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]]             (C4)
-}

(C3)只要x*y子列表中的头部小于当前找到的最大值，就可以停止。这是快捷功能循环代码可以实现的，但不是(C4)，它保证首先找到最大回文数。另外，对于基于列表的代码，它的算法性质在视觉上更加明显，IMO。

haskell - 具有更大域的 Euler #4

6 回答 6

列表不是循环！

Related

Reference