نمط haskell / الكفاءة

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) لكل عدد صحيح (الذي أنا فكر في يتطلب العمل على ترتيب عدد الأعداد الأولية التي وجدناها حتى الآن)، ويحدثها فقط عندما نواجه رئيسا جديدا.

فقط من اختبارات غير علمية (قيد التشغيل take 1000 في GHCI) يبدو primes3 يعمل بشكل أسرع من primes2.

هل يجب أن أحمل درسا من هذا، وافترض أنه إذا كان بإمكاني تمثيل وظيفة كعملية على صفيف، يجب أن أقوم بتطبيقها بطريقة أخرى للكفاءة، أم أن هناك شيئا آخر يحدث هنا؟

Answer 1

ما هي الحجة الثانية ل fهناك حاجة ل؟ في رأيي، كل من هذه البدائل أكثر قابلية للقراءة، ولا تؤثر بشكل كبير على الأداء ...

...
            let g y = f y && y `mod` x > 0 in
            x : mkPrimes g xs
...

import Control.Arrow  -- instance Monad (-> r)
import Control.Monad  -- liftM2
(.&&.) = liftM2 (&&)
...
            let g y = y `mod` x > 0 in
            x : mkPrimes (f .&&. g) xs
...

---

على أي حال، العودة إلى السؤال. في بعض الأحيان استخدام الوظائف لأن هياكل البيانات هي أفضل تمثيل لمهمة معينة، وأحيانا لا. "الأفضل" من حيث الترميز و "الأفضل" من حيث الأداء ليست دائما نفس الشيء. "وظائف كهياكل البيانات" هي ضرورية ل تجميع وقت التشغيل, ، ولكن كما تحذر تلك الصفحة،

يمكن تجميع وقت التشغيل أحيانا الفوز بك مكاسب الكفاءة الكبيرة، ولكن يمكن أن يفوز لك في كثير من الأحيان في أي شيء تقريبا بتكلفة الإجهاد المتزايد وتقليل الإنتاجية.

في حالتك، من المحتمل أن يكون الهدف من بناء كل f :: Integer -> ... -> Bool هو أعلى بكثير من النفقات العامة لبناء كل ps :: [Integer], مع اختلاف قليل أو لا يحدث عند الاتصال f ... x عكس all ... ps.

---

للضغط على الدورات من المنخل الرئيسي لانهائي، تخلص من المكالمات modفي عدد صحيح الضرب والقسمة والمعامل أبطأ بكثير من إضافة عدد صحيح والطرح. على جهازي، فإن ساعات التنفيذ هذه في 40٪ أسرع عند حساب أول 1000 بريمات (GHC 6.10.3 -O2).

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). وبعد الجري (++) هو خطي في طول حجتها اليسرى، ولكن ثابت في طول الحجة الصحيحة.