6

projecteuler.net の問題 #31 [ SPOILERS AHEAD ] (イギリスの硬貨で 2£ を作る方法の数を数える) を解決する際に、動的計画法を使用したいと考えました。私は OCaml から始めて、短くて非常に効率的な次のプログラミングを書きました。

open Num

let make_dyn_table amount coins =
  let t = Array.make_matrix (Array.length coins) (amount+1) (Int 1) in
  for i = 1 to (Array.length t) - 1 do
    for j = 0 to amount do
      if j < coins.(i) then
        t.(i).(j) <- t.(i-1).(j)
      else
        t.(i).(j) <- t.(i-1).(j) +/ t.(i).(j - coins.(i))
    done
  done;
  t

let _ =
  let t = make_dyn_table 200 [|1;2;5;10;20;50;100;200|] in
  let last_row = Array.length t - 1 in
  let last_col = Array.length t.(last_row) - 1 in
  Printf.printf "%s\n" (string_of_num (t.(last_row).(last_col)))

これは、私のラップトップで約 8 ミリ秒で実行されます。金額を 200 ペンスから 100 万ペンスに増やしても、プログラムは 2 秒以内に答えを見つけます。

私はプログラムを Haskell に変換しました (それ自体はまったく面白くありませんでした)。200 ペンスの正しい答えで終了しますが、その数を 10000 に増やすと、私のラップトップはきしみ音を立てて停止します (多くのスラッシング)。コードは次のとおりです。

import Data.Array

createDynTable :: Int -> Array Int Int -> Array (Int, Int) Int
createDynTable amount coins =
    let numCoins = (snd . bounds) coins
        t = array ((0, 0), (numCoins, amount))
            [((i, j), 1) | i <- [0 .. numCoins], j <- [0 .. amount]]
    in t

populateDynTable :: Array (Int, Int) Int -> Array Int Int -> Array (Int, Int) Int
populateDynTable t coins =
    go t 1 0
        where go t i j
                 | i > maxX = t
                 | j > maxY = go t (i+1) 0
                 | j < coins ! i = go (t // [((i, j), t ! (i-1, j))]) i (j+1)
                 | otherwise = go (t // [((i, j), t!(i-1,j) + t!(i, j - coins!i))]) i (j+1)
              ((_, _), (maxX, maxY)) = bounds t

changeCombinations amount coins =
    let coinsArray = listArray (0, length coins - 1) coins
        dynTable = createDynTable amount coinsArray
        dynTable' = populateDynTable dynTable coinsArray
        ((_, _), (i, j)) = bounds dynTable
    in
      dynTable' ! (i, j)

main =
    print $ changeCombinations 200 [1,2,5,10,20,50,100,200]

Haskell をよく知っている人から、なぜこのソリューションのパフォーマンスが悪いのかを聞きたいです。

4

2 に答える 2

11

Haskell は純粋です。純度は、値が不変であることを意味するため、ステップで

j < coins ! i = go (t // [((i, j), t ! (i-1, j))]) i (j+1)

更新するエントリごとに新しい配列全体を作成します。2 ポンドのような少額の場合、それはすでに非常に高価ですが、100 ポンドの金額ではまったくわいせつになります。

さらに、配列はボックス化されています。つまり、配列にはエントリへのポインターが含まれているため、局所性が悪化し、より多くのストレージを使用し、最終的に強制されたときに評価が遅くなるサンクを構築できます。

使用されるアルゴリズムは、その効率のために変更可能なデータ構造に依存しますが、変更可能性は計算に限定されるため、一時的に変更可能なデータ、ST状態変換モナド ファミリー、および関連する [unboxed 、効率のために]配列。

sを使用してアルゴリズムをコードに変換するのに 30 分ほど時間をください。そうすればSTUArray、あまり醜くなく、O'Caml バージョンと同等のパフォーマンスを発揮する Haskell バージョンが得られます (多かれ少なかれ一定の係数が期待されます)。違いについては、1より大きいか小さいかはわかりません)。

ここにあります：

module Main (main) where

import System.Environment (getArgs)

import Data.Array.ST
import Control.Monad.ST
import Data.Array.Unboxed

standardCoins :: [Int]
standardCoins = [1,2,5,10,20,50,100,200]

changeCombinations :: Int -> [Int] -> Int
changeCombinations amount coins = runST $ do
    let coinBound = length coins - 1
        coinsArray :: UArray Int Int
        coinsArray = listArray (0, coinBound) coins
    table <- newArray((0,0),(coinBound, amount)) 1 :: ST s (STUArray s (Int,Int) Int)
    let go i j
            | i > coinBound = readArray table (coinBound,amount)
            | j > amount   = go (i+1) 0
            | j < coinsArray ! i = do
                v <- readArray table (i-1,j)
                writeArray table (i,j) v
                go i (j+1)
            | otherwise = do
                v <- readArray table (i-1,j)
                w <- readArray table (i, j - coinsArray!i)
                writeArray table (i,j) (v+w)
                go i (j+1)
    go 1 0

main :: IO ()
main = do
    args <- getArgs
    let amount = case args of
                   a:_ -> read a
                   _   -> 200
    print $ changeCombinations amount standardCoins

あまりぎこちない時間で実行され、

$ time ./mutArr
73682

real    0m0.002s
user    0m0.000s
sys     0m0.001s
$ time ./mutArr 1000000
986687212143813985

real    0m0.439s
user    0m0.128s
sys     0m0.310s

チェックされた配列アクセスを使用し、チェックされていないアクセスを使用すると、時間が多少短縮される可能性があります。

ああ、あなたの O'Caml コードは任意精度の整数を使っていることを知りました。そのためInt、Haskell で使用すると O'Caml が不当に不利になります。任意の精度Integers で結果を計算するために必要な変更は最小限です。

$ diff mutArr.hs mutArrIgr.hs
12c12
< changeCombinations :: Int -> [Int] -> Int
---
> changeCombinations :: Int -> [Int] -> Integer
17c17
<     table <- newArray((0,0),(coinBound, amount)) 1 :: ST s (STUArray s (Int,Int) Int)
---
>     table <- newArray((0,0),(coinBound, amount)) 1 :: ST s (STArray s (Int,Int) Integer)
28c28
<                 writeArray table (i,j) (v+w)
---
>                 writeArray table (i,j) $! (v+w)

適応する必要があるのは 2 つの型シグネチャのみです。配列は必然的にボックス化されるため、28 行目で配列にサンクを書き込まないようにする必要があります。

$ time ./mutArrIgr 
73682

real    0m0.002s
user    0m0.000s
sys     0m0.002s
$ time ./mutArrIgr 1000000
99341140660285639188927260001

real    0m1.314s
user    0m1.157s
sys     0m0.156s

sに対してオーバーフローした大きな結果の計算には、Int著しく時間がかかりますが、予想どおり、O'Caml に匹敵します。

O'Caml を理解するのに少し時間を費やすと、より近く、少し短く、間違いなくより良い翻訳を提供できます。

module Main (main) where

import System.Environment (getArgs)

import Data.Array.ST
import Control.Monad.ST
import Data.Array.Unboxed
import Control.Monad (forM_)

standardCoins :: [Int]
standardCoins = [1,2,5,10,20,50,100,200]

changeCombinations :: Int -> [Int] -> Integer
changeCombinations amount coins = runST $ do
    let coinBound = length coins - 1
        coinsArray :: UArray Int Int
        coinsArray = listArray (0, coinBound) coins
    table <- newArray((0,0),(coinBound, amount)) 1 :: ST s (STArray s (Int,Int) Integer)
    forM_ [1 .. coinBound] $ \i ->
        forM_ [0 .. amount] $ \j ->
            if j < coinsArray!i
              then do
                  v <- readArray table (i-1,j)
                  writeArray table (i,j) v
              else do
                v <- readArray table (i-1,j)
                w <- readArray table (i, j - coinsArray!i)
                writeArray table (i,j) $! (v+w)
    readArray table (coinBound,amount)

main :: IO ()
main = do
    args <- getArgs
    let amount = case args of
                   a:_ -> read a
                   _   -> 200
    print $ changeCombinations amount standardCoins

ほぼ同じ速度で実行されます。

$ time ./mutArrIgrM 1000000
99341140660285639188927260001

real    0m1.440s
user    0m1.273s
sys     0m0.164s
于 2012-12-14T01:33:37.387 に答える
4

Haskell が遅延していることを利用して、自分で配列を満たすスケジュールを設定するのではなく、適切な順序で実行するために遅延評価に頼ることができます。(入力が大きい場合は、スタック サイズを増やす必要があります。)

import Data.Array

createDynTable :: Integer -> Array Int Integer -> Array (Int, Integer) Integer
createDynTable amount coins =
    let numCoins = (snd . bounds) coins
        t = array ((0, 0), (numCoins, amount))
            [((i, j), go i j) | i <- [0 .. numCoins], j <- [0 .. amount]]
        go i j | i == 0        = 1
               | j < coins ! i = t ! (i-1, j)
               | otherwise     = t ! (i-1, j) + t ! (i, j - coins!i)
    in t


changeCombinations amount coins =
    let coinsArray = listArray (0, length coins - 1) coins
        dynTable = createDynTable amount coinsArray
        ((_, _), (i, j)) = bounds dynTable
    in
       dynTable ! (i, j)

main =
    print $ changeCombinations 200 [1,2,5,10,20,50,100,200]
于 2012-12-14T09:55:45.470 に答える