हास्केल शैली/दक्षता

Question

तो मैं आलसी उत्पन्न करने के तरीके पर काम कर रहा था, और मैं इन तीन परिभाषाओं के साथ आया, जो सभी समान तरीके से काम करते हैं - सिर्फ यह जांचते हैं कि प्रत्येक नए पूर्णांक में पिछले सभी के बीच एक कारक है अभाज्य संख्या:

primes1 :: [Integer] 
primes1 = mkPrimes id [2..] 
    where mkPrimes f (x:xs) = 
      if f (const True) x 
      then 
      let g h y = y `mod` x > 0 && h y in 
      x : mkPrimes (f . g) xs 
      else 
      mkPrimes f xs 

primes2 :: [Integer] 
primes2 = mkPrimes id (const True) [2..] 
    where mkPrimes f f_ (x:xs) = 
      if f_ x 
      then 
      let g h y = y `mod` x > 0 && h y in 
      x : mkPrimes (f . g) (f $ g $ const True) xs 
      else 
      mkPrimes f f_ xs 

primes3 :: [Integer] 
primes3 = mkPrimes [] [2..] 
    where mkPrimes ps (x:xs) = 
      if all (\p -> x `mod` p > 0) ps 
      then 
      x : mkPrimes (ps ++ [x]) xs 
      else 
      mkPrimes ps xs 

तो मुझे लगता है primes2, primes1 की तुलना में थोड़ा तेजी से किया जाना चाहिए, क्योंकि यह हर पूर्णांक (जो मुझे लगता है कि के लिए f_ = f (const True) recomputing अभाज्य संख्या की संख्या के आदेश पर काम की आवश्यकता है से बचा जाता है हम अब तक पाया गया है), और जब हम एन्क करते हैं तो केवल अपडेट होते हैं एक नया प्रधान काउंटर।

बस अवैज्ञानिक परीक्षण से (GHCi में take 1000 चल) यह primes3 रन तेजी से primes2 से की तरह लगता है।

मैं इस से एक सबक लग सकते हैं और मानते हैं कि अगर मैं एक सरणी पर एक आपरेशन के रूप में एक समारोह का प्रतिनिधित्व कर सकते हैं, कि मैं यह दक्षता के लिए बाद ढंग से लागू करना चाहिए, या वहाँ कुछ किसी और यहाँ पर जा रहा है ?

Answer 1

f की आवश्यकता के लिए दूसरा तर्क क्या है? मेरी राय में, इन विकल्पों के दोनों अधिक पठनीय हैं, और काफी प्रदर्शन को प्रभावित नहीं है ...

---

किसी भी तरह, वापस सवाल का। कभी-कभी डेटा संरचनाओं के रूप में कार्यों का उपयोग करना एक निश्चित कार्य के लिए सबसे अच्छा प्रतिनिधित्व है, और कभी-कभी नहीं। प्रदर्शन के संदर्भ में आसानी से कोडिंग और "सर्वश्रेष्ठ" के मामले में "सर्वश्रेष्ठ" हमेशा एक ही चीज़ नहीं होती है। "डेटा संरचनाओं के रूप में कार्य" तकनीक runtime compilation के लिए आवश्यक है, लेकिन जैसा कि उस पृष्ठ चेतावनी देते हैं,

क्रम संकलन कभी कभी आप महत्वपूर्ण दक्षता लाभ जीत सकते हैं, लेकिन अक्सर आप अपनी वृद्धि हुई तनाव की कीमत पर लगभग कुछ भी नहीं जीत सकते हैं और उत्पादकता कम हो गई।

आपके मामले में, यह संभव है कि प्रत्येक f :: Integer -> ... -> Bool के निर्माण की भूमि के ऊपर जब f ... x बनाम all ... ps बुला कम या कोई अंतर के साथ प्रत्येक ps :: [Integer], के निर्माण की भूमि के ऊपर से काफी अधिक है।

---

अनंत प्रधानमंत्री चलनी से बाहर चक्र निचोड़ करने के लिए, mod के लिए कॉल से छुटकारा पाने के! इंटीजर गुणा, विभाजन, और मॉड्यूलस पूर्णांक अतिरिक्त और घटाव से बहुत धीमी हैं। मेरी मशीन पर, पहले 1000 प्राइम्स (जीएचसी 6.10.3 -O2) की गणना करते समय, यह कार्यान्वयन 40% तेज होता है।

import qualified Data.Map as M 
primes' :: [Integer] 
primes' = mkPrimes 2 M.empty 
    where 
    mkPrimes n m = case (M.null m, M.findMin m) of 
     (False, (n', skips)) | n == n' -> 
      mkPrimes (succ n) (addSkips n (M.deleteMin m) skips) 
     _ -> n : mkPrimes (succ n) (addSkip n m n) 
    addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m 
    addSkips = foldl' . addSkip 

कार्रवाई में (JSON-ish वाक्य रचना का एक सा प्रयोग करके),

mkPrimes 2 {} 
=> 2 : mkPrimes 3 {4: [2]} 
=> 2 : 3 : mkPrimes 4 {4: [2], 6: [3]} 
=> 2 : 3 : mkPrimes 5 {6: [2, 3]} 
=> 2 : 3 : 5 : mkPrimes 6 {6: [2, 3], 10: [5]} 
=> 2 : 3 : 5 : mkPrimes 7 {8: [2], 9: [3], 10: [5]} 
=> 2 : 3 : 5 : 7 : mkPrimes 8 {8: [2], 9: [3], 10: [5], 14: [7]} 
=> 2 : 3 : 5 : 7 : mkPrimes 9 {9: [3], 10: [2, 5], 14: [7]} 
=> 2 : 3 : 5 : 7 : mkPrimes 10 {10: [2, 5], 12: [3], 14: [7]} 
=> 2 : 3 : 5 : 7 : mkPrimes 11 {12: [2, 3], 14: [7], 15: [5]} 
... 

नक्शा रहता है भविष्य गुणकों का ट्रैक है, लेकिन इसके अलावा कुछ भी नहीं है का उपयोग कर।

Answer 2

ध्यान दें कि primes3 को ps++[x] से (x:ps) पर बदलकर और अधिक कुशल बनाया जा सकता है।चल रहे (++) अपने बाएं तर्क की लंबाई में रैखिक है, लेकिन सही तर्क की लंबाई में निरंतर है।