हास्केल में गतिशील प्रोग्रामिंग का उपयोग करना? [चेतावनी: ProjectEuler 31 समाधान अंदर]

Question

projecteuler.net की समस्या को हल करने में # 31 [स्पोइलर्स अहिड] (ब्रिटिश सिक्कों के साथ 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))) 

यह मेरा लैपटॉप पर ~ 8ms में निष्पादित करता है। यदि मैं 200 पेंस से दस लाख तक की राशि बढ़ाता हूं, तो प्रोग्राम को अभी भी दो सेकंड से भी कम समय में एक जवाब मिल जाता है।

मैंने प्रोग्राम को हास्केल (जो कि निश्चित रूप से मजेदार नहीं था) में अनुवाद किया है, और हालांकि यह 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] 

मैं किसी को जो हास्केल अच्छी तरह से जानता कि क्यों इस समाधान का प्रदर्शन इतना बुरा है से सुनने के लिए खुशी होगी: यहाँ कोड है।

Answer 1

हास्केल शुद्ध है। पवित्रता का मतलब है कि मूल्यों कदम

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

आप प्रत्येक प्रविष्टि से आपको अवगत कराने के लिए एक पूरी नई सरणी बनाने में अडिग हैं, और इस तरह। £ 2 की तरह छोटी राशि के लिए यह पहले से ही महंगा है, लेकिन यह £ 100 की राशि के लिए पूरी तरह से अश्लील हो जाता है।

इसके अलावा, सरणी बॉक्स किए गए हैं, इसका मतलब है कि उनमें प्रविष्टियों के पॉइंटर्स होते हैं, जो इलाके को खराब करते हैं, अधिक भंडारण का उपयोग करते हैं, और थंक्स को बनाने की अनुमति देते हैं जो आखिरकार मजबूर होने पर मूल्यांकन करने के लिए धीमे होते हैं। , ST राज्य ट्रांसफार्मर इकाई परिवार

एल्गोरिथ्म अपनी क्षमता के लिए एक परिवर्तनशील डेटा संरचना पर निर्भर करता है, लेकिन अस्थिरता गणना तक ही सीमित है, इसलिए हम क्या अस्थायी रूप से परिवर्तनशील डेटा के साथ सुरक्षित रूप से परिरक्षित संगणना अनुमति देने के लिए करना है उपयोग कर सकते हैं, और संबंधित [unboxed, दक्षता के लिए] सरणी।

STUArray एस का उपयोग करके कोड में एल्गोरिदम का अनुवाद करने के लिए मुझे आधे घंटे या उससे अधिक समय दें, और आपको एक हास्केल संस्करण मिलेगा जो बहुत बदसूरत नहीं है, और ओ'कैम संस्करण (कुछ और अधिक) अंतर के लिए कम निरंतर कारक की उम्मीद है, चाहे वह 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 एक अनुचित नुकसान पर O'Caml डालता है का उपयोग कर सीखा है।मनमाने ढंग से सटीक Integer रों आपके minmal हैं के साथ परिणाम की गणना करने के लिए आवश्यक परिवर्तन,

$ 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) 

केवल दो प्रकार के लिए अनुकूलित किया जा करने के लिए आवश्यक हस्ताक्षर - सरणी जरूरी बॉक्सिंग हो जाता है, तो हम बनाने की जरूरत है यकीन है कि हम नहीं लिख रहे हैं लाइन 28 में सरणी Thunks, और

$ 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 

बड़े नतीजा यह है कि Int रों लिए overflowed साथ गणना काफ़ी समय लगता है, लेकिन 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 

Answer 2

---

कुछ समय O'Caml समझने खर्च, मैं एक करीबी, थोड़ा कम, और यकीनन अच्छे अनुवाद पेशकश कर सकते हैं

आप हास्केल को आलसी होने का लाभ उठा सकते हैं और खुद को भरने वाले सरणी को शेड्यूल नहीं कर सकते हैं, बल्कि इसके बजाय सही क्रम में करने के लिए आलसी मूल्यांकन पर भरोसा करते हैं। अगर मैं हास्केल में खरोंच से इस लिख रहे थे, (बड़े आदानों के लिए आप ढेर आकार बढ़ाने के लिए की आवश्यकता होगी।)

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]