हास्केल में कुशल डायनामिक प्रोग्रामिंग एल्गोरिदम कैसे लिखता है?

Question

मैं हास्केल में गतिशील प्रोग्रामिंग के साथ खेल रहा हूं। इस विषय पर मैंने जो व्यावहारिक रूप से देखा है, वही, बहुत ही सुरुचिपूर्ण एल्गोरिदम देता है जो ज्ञापन और आरे प्रकार की आलस्य पर आधारित होता है। उन उदाहरणों से प्रेरित, मैंने निम्नलिखित एल्गोरिदम को एक परीक्षण के रूप में लिखा:

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

मेरी एकमात्र समस्या दक्षता है। यहां तक ​​कि जीएचसी के-ओ 2 का उपयोग करके, इस कार्यक्रम को pascal 1000 की गणना करने के लिए 1.6 सेकंड लगते हैं, जो समकक्ष अपरिवर्तित सी ++ प्रोग्राम की तुलना में 160 गुना धीमी है। और अंतर केवल बड़े इनपुट के साथ बढ़ता है।

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

1. उपरोक्त कोड इतना अक्षम क्यों है? यह प्रत्येक प्रविष्टि पर अंकगणितीय ऑपरेशन के साथ, एक मैट्रिक्स के माध्यम से एक सीधा पुनरावृत्ति की तरह लगता है। जाहिर है हास्केल उन दृश्यों के पीछे कुछ कर रहा है जिन्हें मैं समझ नहीं पा रहा हूं।

2. क्या इसके स्टेटलेस, रिकर्सिव फॉर्मूलेशन को बलि किए बिना इसे अधिक कुशल बनाने के लिए कोई अधिक कुशल (एक सी प्रोग्राम के रनटाइम पर 10-15 बार) बनाने का कोई तरीका है (एसटी में परिवर्तनीय सरणी का उपयोग करके कार्यान्वयन के साथ-साथ इकाई)?

बहुत बहुत धन्यवाद।

संपादित करें: सारणी का प्रयोग किया मॉड्यूल मानक Data.Array

Answer 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 पैकेज में शामिल हैं का अनुकूलन: vector पैकेज का उपयोग करते हुए और एक बार में केवल स्मृति में एक पंक्ति रखने के बारे में स्मार्ट किया जा रहा है, हम कुछ है कि एक अलग तरीके से मुहावरेदार है प्राप्त कर सकते हैं एक बेवकूफ शैली में लिखे गए सरणी संचालन को पारदर्शी रूप से अनुकूलित करने के लिए कुछ सरल चालें।

Answer 2

1 है क्यों उपरोक्त कोड तो अक्षम है? यह प्रत्येक प्रविष्टि पर अंकगणितीय ऑपरेशन के साथ, एक मैट्रिक्स के माध्यम से एक सीधा पुनरावृत्ति की तरह लगता है। जाहिर है हास्केल उन दृश्यों के पीछे कुछ कर रहा है जिन्हें मैं समझ नहीं पा रहा हूं।

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

सी ++ कोड में यह समस्या नहीं है, मान लिखे गए हैं, और बिना आगे मूल्यांकन की आवश्यकता के सीधे पढ़ें। जैसा कि यह 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 वहाँ यह बहुत अधिक कुशल बनाने के लिए एक रास्ता है (सबसे 10-15 गुना पर एक सी कार्यक्रम के क्रम) की तुलना में एक की तुलना में एक कार्यान्वयन में परिवर्तनशील सरणियों का उपयोग कर अपने राज्यविहीन, पुनरावर्ती सूत्रीकरण त्याग (बिना एसटी मोनाद)?

मुझे एक के बारे में पता नहीं है। लेकिन हो सकता है।

परिशिष्ट:

एक STUArray या अनबॉक्स्ड Vector रों का उपयोग करता है एक बार, वहां अभी भी बराबर सी कार्यान्वयन के लिए एक महत्वपूर्ण अंतर है। इसका कारण यह है कि मॉड्यूल ज्ञात होने के बाद, गुणा गुणा, शिफ्ट और घटाव (यहां तक ​​कि बिना अनुकूलन के) के संयोजन से % को प्रतिस्थापित करता है। हास्केल में हाथ से ही कर रहा है (क्योंकि GHC नहीं करता [अभी तक] है कि),

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

सी

Answer 3

यह चाल एक बार में पूरे लानत एल्गोरिदम को लिखने के बारे में सोचना है, और फिर अपने बैकिंग डेटा प्रकार के रूप में अनबॉक्स किए गए वैक्टर का उपयोग करें। उदाहरण के लिए, निम्नलिखित के बारे में 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 में भाग गए।

pascal' :: Integer -> Integer 
pascal :: Int -> Int 
pascal' n = product [n+1..n*2] `div` product [2..n] 
pascal = fromIntegral . (`mod` 1000000) . pascal' . fromIntegral