23

我一直在玩 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. 有没有办法在不牺牲其无状态、递归公式（相对于在 ST Monad 中使用可变数组的实现）的情况下使其更高效（最多是 C 程序运行时间的 10-15 倍）？

非常感谢。

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

4

3 回答 3

17

好吧，算法可以设计得更好一点。使用该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包包含一些相当巧妙的技巧来透明地优化以惯用风格​​编写的数组操作。

于 2012-06-06T00:06:36.570 回答
9

1 为什么上面的代码效率这么低？这似乎是对矩阵的简单迭代，每个条目都有一个算术运算。显然，Haskell 在幕后做了一些我不明白的事情。

问题是代码将 thunk 写入数组。然后，当读取条目时(n,n)，对 thunk 的评估再次在整个数组中跳跃，循环直到最终找到不需要进一步递归的值。这会导致大量不必要的分配和低效率。

C++ 代码没有这个问题，值被写入并直接读取，无需进一步评估。就像STUArray. 做

p = runSTUArray $ do
    arr <- newArray ((0,0),(n,n)) 1
    forM_ [1 .. n] $ \i ->
        forM_ [1 .. n] $ \j -> do
            a <- readArray arr (i,j-1)
            b <- readArray arr (i-1,j)
            writeArray arr (i,j) $! (a+b) `rem` 1000000
    return arr

真的长得这么差吗？

2 有没有办法在不牺牲其无状态的递归公式（相对于在 ST Monad 中使用可变数组的实现）的情况下使其更高效（最多是 C 程序运行时间的 10-15 倍）？

我不知道一个。但可能有。

附录：

一旦使用STUArrays 或 unboxed Vectors，与等效的 C 实现仍然存在显着差异。原因是 gcc 用%乘法、移位和减法的组合替换 （即使没有优化），因为模数是已知的。在 Haskell 中手动做同样的事情（因为 GHC 还没有这样做），

-- fast modulo 1000000
-- for nonnegative Ints < 2^31
-- requires 64-bit Ints
fastMod :: Int -> Int
fastMod n = n - 1000000*((n*1125899907) `shiftR` 50)

获得与 C 相当的 Haskell 版本。

于 2012-06-05T23:42:42.810 回答
9

诀窍是考虑如何一次编写整个该死的算法，然后使用未装箱的向量作为支持数据类型。例如，以下代码在我的机器上的运行速度比您的代码快 20 倍：

import qualified Data.Vector.Unboxed as V

combine :: Int -> Int -> Int
combine x y = (x+y) `mod` 1000000

pascal n = V.last $ go n where
    go 0 = V.replicate (n+1) 1
    go m = V.scanl1 combine (go (m-1))

然后我写了两个main函数调用你的和我的，参数为 4000；10.42s这些分别跑进来0.54s。当然，我相信你知道，它们都被0.00s使用更好算法的版本从水中吹走了（ ）：

pascal' :: Integer -> Integer
pascal :: Int -> Int
pascal' n = product [n+1..n*2] `div` product [2..n]
pascal = fromIntegral . (`mod` 1000000) . pascal' . fromIntegral
于 2012-06-06T01:01:18.287 回答