performance - 如何在 Haskell 中编写高效的动态规划算法？

Question

我一直在研究 Haskell 中的动态编程。实际上，我所看到的关于该主题的每个教程都给出了相同的、非常优雅的算法，该算法基于内存和 Array 类型的惰性。受这些例子的启发，我编写了以下算法作为测试:

-- pascal n returns the nth entry on the main diagonal of pascal's triangle
-- (mod a million for efficiency)
pascal :: Int -> Int
pascal n  = p ! (n,n) where
           p = listArray ((0,0),(n,n)) [f (i,j) | i <- [0 .. n], j <- [0 .. n]]

           f :: (Int,Int) -> Int
           f (_,0) = 1
           f (0,_) = 1
           f (i,j) = (p ! (i, j-1) + p ! (i-1, j)) `mod` 1000000 

我唯一的问题是效率。即使使用 GHC 的 -O2，该程序也需要 1.6 秒来计算 pascal 1000，这比等效的未优化 C++ 程序慢大约 160 倍。差距只会随着投入的增加而扩大。

似乎我已经尝试了上述代码的每一种可能排列，以及建议的替代方案，如 data-memocombinators 库，它们都具有相同或更差的性能。我没有尝试过的一件事是 ST Monad，我确信可以让它运行程序只比 C 版本慢一点。但我真的很想用惯用的 Haskell 来写它，我不明白为什么惯用版本的效率如此低下。我有两个问题:

1. 为什么上面的代码这么低效？这似乎是对矩阵的直接迭代，在每个条目处进行算术运算。很明显，Haskell 在幕后做了一些我不明白的事。

2. 有没有办法在不牺牲其无状态、递归公式(相对于在圣莫纳德)？

非常感谢。

编辑:使用的数组模块是标准的Data.Array

Answer 1

嗯，算法可以设计得更好一点。使用 vector 包并聪明地一次只在内存中保留一行，我们可以用不同的方式获得一些惯用的东西:

{-# LANGUAGE BangPatterns #-}
import Data.Vector.Unboxed
import Prelude hiding (replicate, tail, scanl)

pascal :: Int -> Int
pascal !n = go 1 ((replicate (n+1) 1) :: Vector Int) where
  go !i !prevRow
    | i <= n    = go (i+1) (scanl f 1 (tail prevRow))
    | otherwise = prevRow ! n
  f x y = (x + y) `rem` 1000000

这优化非常紧密，特别是因为 vector 包包含一些相当巧妙的技巧，可以透明地优化以惯用风格​​编写的数组操作。