2012-06-04 12 views
12

मैंने और C++ (ideone लिंक) दोनों में Project Euler's Challenge 14 के लिए कोड लिखा है। वे दोनों किसी भी गणना में पहले से किए गए किसी भी गणना को याद करते हैं।जीएचसी अनुकूलन: कोलाट्स अनुमान

क्रमशः ghc -O2 और g++ -O3 का उपयोग करके, सी ++ हास्केल संस्करण की तुलना में 10-15 गुना तेजी से चलता है।

जबकि मैं समझता हूं कि हास्केल संस्करण धीमा हो सकता है, और हैस्केल लिखने के लिए एक अच्छी भाषा है, यह कुछ अच्छा परिवर्तन जानना अच्छा होगा, जिसे मैं हास्केल संस्करण में तेज़ी से चलाने के लिए कर सकता हूं (आदर्श रूप से सी ++ संस्करण के 2 या 3 का कारक)?


हास्केल कोड यहाँ है:

import Data.Array 
import Data.Word 
import Data.List 

collatz_array = 
    let 
    upperbound = 1000000 
    a = array (1, upperbound) [(i :: Word64, f i :: Int) | i <- [1..upperbound]] 
    f i = i `seq` 
     let 
     check_f i = i `seq` if i <= upperbound then a ! i else f i 
     in 
     if (i == 1) then 0 else (check_f ((if (even i) then i else 3 * i + 1) `div` 2)) + 1 
    in a 

main = 
    putStrLn $ show $ 
    foldl1' (\(x1,x2) (y1,y2) -> if (x2 >= y2) then (x1, x2) else (y1, y2)) $! (assocs collatz_array) 

संपादित करें:

मैं अब भी अनबॉक्स्ड परिवर्तनशील सरणियों का उपयोग कर एक संस्करण किया है। यह अभी भी सी ++ संस्करण की तुलना में 5 गुना धीमा है, लेकिन एक महत्वपूर्ण सुधार है। कोड here पर विचार है।

मैं म्यूटेबल सरणी संस्करण में सुधार जानना चाहता हूं जो इसे सी ++ संस्करण के करीब लाता है।

+0

बस FYI, '-fllvm' के साथ संकलन, मेरी मशीन पर ~ 10% द्वारा प्रदर्शन में सुधार करता है। –

+0

आपकी 'seq' कोई फर्क नहीं पड़ता; आपके दोनों कार्य 'i' में सख्त हैं। 32-बिट प्लेटफ़ॉर्म पर 64-बिट अंकगणित पर जीएचसी काफी खराब था, लेकिन मुझे नहीं पता कि आप किस प्लेटफ़ॉर्म का उपयोग कर रहे हैं। – augustss

+4

'div' का प्रयोग न करें, 'quot' का उपयोग करें। – augustss

उत्तर

4

अपने (परिवर्तनशील सरणी) कोड के साथ कुछ समस्याएं:

  • आप एक गुना का उपयोग अधिकतम श्रृंखला लंबाई खोजने के लिए, इसके लिए सरणी को एक एसोसिएशन सूची में परिवर्तित करना होगा, जिसमें समय और आवंटन को C++ संस्करण की आवश्यकता नहीं होती है।
  • आप even और div का उपयोग करके 2 से राहत देने के लिए उपयोग करते हैं। ये धीमे हैं। जी ++ दोनों परिचालनों को तेजी से बिट ऑपरेशंस (प्लेटफ़ॉर्म पर जहां कम से कम तेज़ माना जाता है) को अनुकूलित करता है, लेकिन जीएचसी इन निम्न-स्तरीय अनुकूलन (अभी तक) नहीं करता है, इसलिए समय के लिए, उन्हें हाथ से किया जाना है ।
  • आप readArray और writeArray का उपयोग करते हैं। C++ कोड में किए गए अतिरिक्त सीमा-जांच में समय लगता है, एक बार अन्य समस्याओं का सामना करने के बाद, यह चलने वाले समय (मेरे बॉक्स पर 25%) के महत्वपूर्ण हिस्से में है, क्योंकि ऐसा किया जाता है एल्गोरिदम में बहुत सारे पढ़ और लिखते हैं।

शामिल है कि कार्यान्वयन में, मैं

import Data.Array.ST 
import Data.Array.Base 
import Control.Monad.ST 
import Data.Bits 

collatz_array :: ST s (STUArray s Int Int) 
collatz_array = do 
    let upper = 10000000 
    arr <- newArray (0,upper) 0 
    unsafeWrite arr 2 1 
    let check i 
      | upper < i = return arr 
      | i .&. 1 == 0 = do 
       l <- unsafeRead arr (i `shiftR` 1) 
       unsafeWrite arr i (l+1) 
       check (i+1) 
      | otherwise = do 
       let j = (3*i+1) `shiftR` 1 
        find k l 
         | upper < k = find (next k) $! l+1 
         | k < i  = do 
          m <- unsafeRead arr k 
          return (m+l) 
         | otherwise = do 
          m <- unsafeRead arr k 
          if m == 0 
           then do 
            n <- find (next k) 1 
            unsafeWrite arr k n 
            return (n+l) 
           else return (m+l) 
          where 
          next h 
           | h .&. 1 == 0 = h `shiftR` 1 
           | otherwise = (3*h+1) `shiftR` 1 
       l <- find j 1 
       unsafeWrite arr i l 
       check (i+1) 
    check 3 

collatz_max :: ST s (Int,Int) 
collatz_max = do 
    car <- collatz_array 
    (_,upper) <- getBounds car 
    let find w m i 
      | upper < i = return (w,m) 
      | otherwise = do 
       l <- unsafeRead car i 
       if m < l 
        then find i l (i+1) 
        else find w m (i+1) 
    find 1 0 2 

main :: IO() 
main = print (runST collatz_max) 

पाने और समय (दोनों 10 लाख के लिए):

$ time ./cccoll 
8400511 429 

real 0m0.210s 
user 0m0.200s 
sys  0m0.009s 
$ time ./stcoll 
(8400511,429) 

real 0m0.341s 
user 0m0.307s 
sys  0m0.033s 

जो बहुत बुरा नहीं लगती है।

महत्वपूर्ण नोट: कि कोड केवल 64-बिट GHC पर काम करता है (हां, विशेष रूप से, विंडोज पर, आप GHC-7.6.1 या बाद में, पिछले GHCs भी 64-बिट Windows पर थे 32-बिट की जरूरत है) चूंकि इंटरमीडिएट चेन तत्व 32-बिट रेंज से अधिक है। 32-बिट सिस्टम पर, एक कठोर प्रदर्शन लागत पर चेन का पालन करने के लिए, Integer या 64-बिट पूर्णांक प्रकार (Int64 या Word64) का उपयोग करना होगा, क्योंकि मूल 64-बिट ऑपरेशंस (अंकगणितीय और शिफ्ट) को लागू किया गया है 32-बिट जीएचसी (फास्ट विदेशी कॉल में सी कार्यों के लिए विदेशी कॉल, लेकिन अभी भी प्रत्यक्ष मशीन सेशन की तुलना में बहुत धीमी है)।

+0

'(3 * एच + 1)' shiftR' 1' '(shiftR h 1) + h + 1' जैसा ही है जो कुछ मशीनों –

+0

पर तेज़ हो सकता है। मेरे पर एक भरोसेमंद मापनीय अंतर नहीं पैदा करता है, इसलिए यदि कोई अंतर होता है, तो यह यहां प्राकृतिक झटके से छोटा है। लेकिन धीमी गुणा के साथ मशीनों पर, यह निश्चित रूप से कोशिश करने के लिए कुछ है। –

2

आदर्श साइट एक ghc 6.8.2 का उपयोग कर रही है, जो बहुत पुरानी हो रही है। Ghc संस्करण 7.4.1 पर, अंतर बहुत छोटा है।

GHC साथ

:

$ ghc -O2 euler14.hs && time ./euler14 
(837799,329) 
./euler14 0.63s user 0.04s system 98% cpu 0.685 total 

जी ++ के साथ 4.7.0:

$ g++ --std=c++0x -O3 euler14.cpp && time ./a.out 
8400511 429 
./a.out 0.24s user 0.01s system 99% cpu 0.252 total 

मेरे लिए, GHC संस्करण केवल 2.7 गुना C++ संस्करण की तुलना में धीमी है। इसके अलावा, दो कार्यक्रमों ही परिणाम दे रही है नहीं कर रहे हैं ... (नहीं एक अच्छा संकेत है, विशेष रूप से बेंच मार्किंग के लिए)

+0

ओह, मैंने 10 मिलियन पोस्ट किए, 1 मिलियन परीक्षण नहीं। लिंक सही है। ध्यान दें कि सी ++ संस्करण ने 10 लाख 2.7 गुना तेजी से हास्केल की तुलना में 1 मिलियन किया था। – Clinton

संबंधित मुद्दे