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 ライブラリのような提案された代替手段とともに、上記のコードの可能なすべての順列を試したようですが、それらはすべて同じかそれより悪いパフォーマンスでした。私が試していないことの 1 つは、ST モナドです。これは、プログラムを C バージョンよりもわずかに遅く実行するように作成できると確信しています。しかし、慣用的なHaskellで書きたいのですが、なぜ慣用的なバージョンがそれほど効率的でないのか理解できません。2 つの質問があります。

  1. 上記のコードが非効率なのはなぜですか? 各エントリで算術演算を使用して、マトリックスを単純に反復するように見えます。明らかに、Haskell は私が理解できない裏で何かを行っています。

  2. ステートレスで再帰的な定式化を犠牲にすることなく (ST Monad で可変配列を使用する実装と比較して) 効率を大幅に向上させる方法はありますか (C プログラムの実行時間の最大 10 倍から 15 倍)。

どうもありがとう。

編集：使用される配列モジュールは標準の Data.Array です

4

3 に答える 3

17

まあ、アルゴリズムはもう少しうまく設計できます。パッケージを使用して、vector一度に 1 つの行のみをメモリに保持することを賢くすることで、別の方法で慣用的なものを取得できます。

{-# 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

秘訣は、いまいましいアルゴリズム全体を一度に作成する方法を考えてから、ボックス化されていないベクトルをバッキングデータ型として使用することです。たとえば、私のマシンでは、次のコードがコードよりも約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の引数を使用して、あなたと私の関数を呼び出す2つの関数を作成しました。これらはそれぞれ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 に答える
9

1上記のコードが非常に非効率的なのはなぜですか？これは、各エントリで算術演算を使用して、行列を単純に反復するように見えます。明らかに、Haskellは私が理解できない舞台裏で何かをしている。

問題は、コードがサンクを配列に書き込むことです。次に、エントリ(n,n)が読み取られると、サンクの評価が再び配列全体にジャンプし、最終的にそれ以上の再帰を必要としない値が見つかるまで繰り返されます。それは多くの不必要な割り当てと非効率を引​​き起こします。

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モナドの可変配列を使用した実装に対して）を犠牲にすることなく、はるかに効率的に（Cプログラムの実行時間の最大10〜15倍）する方法はありますか？

知りません。しかし、あるかもしれません。

補遺：

STUArraysまたはボックス化されていないsを使用しVectorた後でも、同等の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 に答える