इस हास्केल प्रोग्राम के प्रदर्शन में सुधार कैसे करें?

Question

मैं Project Euler में हास्केल सीखने के तरीके के रूप में समस्याओं के माध्यम से काम कर रहा हूं, और मुझे लगता है कि संकलित होने पर भी, मेरे प्रोग्राम तुलनात्मक सी संस्करण की तुलना में बहुत धीमे हैं। मेरे हास्केल कार्यक्रमों को तेज़ करने के लिए मैं क्या कर सकता हूं?

उदाहरण के लिए, Problem 14 करने के लिए अपने जानवर बल समाधान है:

import Data.Int 
import Data.Ord 
import Data.List 

searchTo = 1000000 

nextNumber :: Int64 -> Int64 
nextNumber n 
    | even n = n `div` 2 
    | otherwise = 3 * n + 1 

sequenceLength :: Int64 -> Int 
sequenceLength 1 = 1 
sequenceLength n = 1 + (sequenceLength next) 
    where next = nextNumber n 

longestSequence = maximumBy (comparing sequenceLength) [1..searchTo] 

main = putStrLn $ show $ longestSequence 

जो चारों ओर 220 सेकंड लेता है, एक "बराबर" जानवर बल सी संस्करण केवल 1.2 सेकंड लेता है।

#include <stdio.h> 

int main(int argc, char **argv) 
{ 
    int longest = 0; 
    int terms = 0; 
    int i; 
    unsigned long j; 

    for (i = 1; i <= 1000000; i++) 
    { 
     j = i; 
     int this_terms = 1; 

     while (j != 1) 
     { 
      this_terms++; 

      if (this_terms > terms) 
      { 
       terms = this_terms; 
       longest = i; 
      } 

      if (j % 2 == 0) 
       j = j/2; 
      else 
       j = 3 * j + 1; 
     } 
    } 

    printf("%d\n", longest); 
    return 0; 
} 

मैं क्या गलत कर रहा हूं? या क्या मुझे लगता है कि हास्केल सी की गति तक भी पहुंच सकता है?

(मैं जीसीसी-ओ 2 के साथ सी संस्करण संकलित कर रहा हूं, और ghc --make -O के साथ हास्केल संस्करण)।

Answer 1

परीक्षण उद्देश्य के लिए मैंने अभी searchTo = 100000 सेट किया है। लिया गया समय 7.34s है। कुछ संशोधन कुछ बड़ा सुधार की ओर जाता है:

1. IntegerInt64 के बजाय का उपयोग करें। यह समय 1.75s में सुधार करता है।

2. एक संचयक का उपयोग करें (आपको अनुक्रम लम्बाई को आलसी दाएं होने की आवश्यकता नहीं है?) 1.54s।

   seqLen2 :: Int -> Integer -> Int 
   seqLen2 a 1 = a 
   seqLen2 a n = seqLen2 (a+1) (nextNumber n) 
   
   sequenceLength :: Integer -> Int 
   sequenceLength = seqLen2 1 
   

3. nextNumberquotRem का उपयोग कर पुनर्लेखन

   , इस प्रकार (div में even में एक बार और एक बार) विभाजन की गणना से बचने के दो बार। 1.27s।

   nextNumber :: Integer -> Integer 
   nextNumber n 
       | r == 0 = q 
       | otherwise = 6*q + 4 
       where (q,r) = quotRem n 2 
   

4. उपयोग Schwartzian transform बजाय maximumBy। maximumBy . comparing की समस्या यह है कि sequenceLength फ़ंक्शन को प्रत्येक मान के लिए एक से अधिक बार बुलाया जाता है। 0.32s।

   longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]] 
   

---

नोट:

• मैं ghc -O साथ संकलन के द्वारा समय की जाँच करें और) +RTS -s के साथ चलाने के
• मेरे मशीन मैक ओएस एक्स 10.6 पर चल रहा है। जीएचसी संस्करण 6.12.2 है। संकलित फ़ाइल i386 आर्किटेक्चर में है।)
• सी समस्या 0.078s पर संबंधित पैरामीटर के साथ चलती है। यह gcc -O3 -m32 के साथ संकलित है।

Answer 2

हास्केल की सूचियां ढेर-आधारित हैं, जबकि आपका सी कोड अत्यधिक तंग है और कोई ढेर उपयोग नहीं करता है। सूचियों पर निर्भरता को हटाने के लिए आपको रिफैक्टर की आवश्यकता है।

Answer 3

तुलना अनुक्रमण अनुक्रम लम्बाई बहुत अधिक हो सकती है। यह मेरा सबसे अच्छा संस्करण है:

type I = Integer 
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show) 

searchTo = 1000000 

nextNumber :: I -> I 
nextNumber n = case quotRem n 2 of 
        (n2,0) -> n2 
        _ -> 3*n+1 

sequenceLength :: I -> Int 
sequenceLength x = count x 1 where 
    count 1 acc = acc 
    count n acc = count (nextNumber n) (succ acc) 

longestSequence = maximum . map (\i -> P (sequenceLength i) i) $ [1..searchTo] 

main = putStrLn $ show $ longestSequence 

जवाब और समय सी की तुलना में धीमी है, लेकिन ऐसा मनमाना परिशुद्धता पूर्णांक का उपयोग करता है:

ghc -O2 --make euler14-fgij.hs 
time ./euler14-fgij 
P 525 837799 

real 0m3.235s 
user 0m3.184s 
sys 0m0.015s 

Answer 4

यहां तक ​​कि अगर मैं थोड़ा देर हो रही है, यहाँ मेरा है, मैंने सूचियों पर निर्भरता को हटा दिया और यह समाधान भी ढेर का उपयोग नहीं करता है।

{-# LANGUAGE BangPatterns #-} 
-- Compiled with ghc -O2 -fvia-C -optc-O3 -Wall euler.hs 
module Main (main) where 

searchTo :: Int 
searchTo = 1000000 

nextNumber :: Int -> Int 
nextNumber n = case n `divMod` 2 of 
    (k,0) -> k 
    _  -> 3*n + 1 

sequenceLength :: Int -> Int 
sequenceLength n = sl 1 n where 
    sl k 1 = k 
    sl k x = sl (k + 1) (nextNumber x) 

longestSequence :: Int 
longestSequence = testValues 1 0 0 where 
    testValues number !longest !longestNum 
    | number > searchTo  = longestNum 
    | otherwise   = testValues (number + 1) longest' longestNum' where 
    nlength = sequenceLength number 
    (longest',longestNum') = if nlength > longest 
     then (nlength,number) 
     else (longest,longestNum) 

main :: IO() 
main = print longestSequence 

मैं ghc -O2 -fvia-C -optc-O3 -Wall euler.hs साथ इस टुकड़े संकलित और यह शुरुआत कार्यान्वयन के 80 की तुलना में 5 सेकंड में चलता है,। यह Integer का उपयोग नहीं करता है, लेकिन क्योंकि मैं 64-बिट मशीन पर हूं, परिणाम धोखा दे सकते हैं।

कंपाइलर इस मामले में सभी इंट को अनबॉक्स कर सकता है, जिसके परिणामस्वरूप वास्तव में तेज़ कोड होता है। यह अब तक देखे गए सभी अन्य समाधानों की तुलना में तेज़ी से चलता है, लेकिन सी अभी भी तेज़ है।

Answer 5

हालांकि यह पहले से ही पुराना है, मुझे चूमने दो, एक महत्वपूर्ण बिंदु है जिसे पहले संबोधित नहीं किया गया है।

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

• सी: 0.3 सेकंड
• मूल हास्केल: 14.24 सेकंड, Integer बजाय Int64 का उपयोग कर: 33.96 सेकंड
• KennyTM के उन्नत संस्करण: 5.55 सेकंड, Int का उपयोग कर: 1.85 सेकंड
• क्रिस Kuklewicz के संस्करण: 5.73 Int का उपयोग करके सेकंड: 1.90 सेकंड
• FUZxxl का संस्करण: 3.56 सेकंड, का उपयोग divMod के बजाय: 1.79 सेकंड

तो हम क्या हैं?

1. तो संकलक (मूल रूप से) यह बदल सकता है एक पाश में
2. पुनर्गणना मत अनुक्रम तुलना
3. के लिए लंबाई div resp का उपयोग न करें एक संचायक के साथ लंबाई की गणना। divMod जब आवश्यक नहीं है, quot resp। quotRem बहुत तेज

अभी भी क्या गुम है?

if (j % 2 == 0) 
    j = j/2; 
else 
    j = 3 * j + 1; 

किसी भी सी संकलक मैं का इस्तेमाल किया है थोड़ा-मास्किंग में परीक्षण j % 2 == 0 बदल देती है और एक प्रभाग अनुदेश का उपयोग नहीं करता। जीएचसी (अभी तक) ऐसा नहीं करता है।तो even n परीक्षण या n `quotRem` 2 कंप्यूटिंग काफी महंगा ऑपरेशन है।

nextNumber :: Integer -> Integer 
nextNumber n 
    | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2 
    | otherwise = 3*n+1 

साथ KennyTM के Integer संस्करण में nextNumber की जगह 3.25 सेकंड के लिए अपने समय चल रहा है कम कर देता है (नोट:! Integer के लिए, n `quot` 2n `shiftR` 1 की तुलना में तेजी है, कि 12.69 सेकंड लेता है)।

Int संस्करण में ऐसा करने से इसके चलने का समय 0.41 सेकेंड तक कम हो जाता है। Int एस के लिए, 2 से विभाजन के लिए बिट-शिफ्ट quot ऑपरेशन से थोड़ा तेज है, जो इसके चलने वाले समय को 0.3 9 सेकेंड तक कम करता है।

सूची के निर्माण (कि सी संस्करण में या तो प्रकट नहीं होता है) को खत्म करना,

module Main (main) where 

import Data.Bits 

result :: Int 
result = findMax 0 0 1 

findMax :: Int -> Int -> Int -> Int 
findMax start len can 
    | can > 1000000 = start 
    | canlen > len = findMax can canlen (can+1) 
    | otherwise = findMax start len (can+1) 
     where 
     canlen = findLen 1 can 

findLen :: Int -> Int -> Int 
findLen l 1 = l 
findLen l n 
    | n .&. 1 == 0 = findLen (l+1) (n `shiftR` 1) 
    | otherwise  = findLen (l+1) (3*n+1) 

main :: IO() 
main = print result 

0,37 सेकंड की चल समय में जिसके परिणामस्वरूप एक और छोटा सा speedup पैदावार,।

तो सी संस्करण के करीब पत्राचार में हैस्केल संस्करण इतना लंबा नहीं लगता है, यह ~ 1.3 का एक कारक है।

ठीक है, निष्पक्ष हो, वहाँ सी संस्करण है कि हास्केल संस्करणों में मौजूद नहीं है में एक अक्षमता है,

if (this_terms > terms) 
{ 
    terms = this_terms; 
    longest = i; 
} 

भीतरी पाश में प्रकट हो। सी संस्करण में आंतरिक लूप से बाहर उठाने से कारक ~ 1.4 बनाने के बाद, इसके चलने का समय 0.27 सेकेंड तक कम हो जाता है।