Haskell: جمع أسرع من الأعداد الأولية

Question

إخلاء المسئولية: أنا أعمل على مشكلة Euler 9.

أنا أضيف بعض أعداد كبيرة جدا، كل الأعداد الأولية من 1 إلى 2 000 000.

تلخيص تلك الأعاصا يستغرق إلى الأبد. أنا أستخدم Haskell المدمج في الوظيفة "Sum".

كما هو الحال في:

sum listOfPrimes

هل هناك أي خيارات أسرع أخرى؟

- كان مولد Prime My هو الرابط البطيء في التعليمات البرمجية الخاصة بي.

Answer 1

يبدو أن مشكلتك لا تلخيص الأرقام، ولكن توليدها. ما هو تنفيذ الخاص بك ل

قد تكون هذه الورقة ذات أهمية: http://lambda-the-ultimate.org/node/3127.

Answer 2

آمل أن تستخدم GHC -O2 وليس GHCI، أليس كذلك؟ مشكلتك ستكون في الجيل، وليس التلخيص.

طريقة أسرع واحدة هي استخدام تسلسلات قائمة على الاندماج، والتي تتحسن أفضل. مع قوائم منتظمة:

import Data.List
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

-- fuse:
main = print (sum (takeWhile (<= 2000000) primes))

نحن نحصل،

$ ghc -O2 --make A.hs
$ time ./A           
142913828922
./A  9.99s user 0.17s system 99% cpu 10.166 total

التبديل إلى الجداول، مبلغ جدا. الصمامات الحاشية:

import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))

يحفظ بعض الوقت الصغيرة،

$ time ./A           
142913828922
./A  9.60s user 0.13s system 99% cpu 9.795 total

لكن مشكلتك ستكون جيلا رئيسيا، حيث يمكننا أن نرى ما إذا كنا نتجاهل التلخيص تماما، واستبدال المبلغ الأخير:

$ time ./A           
1999993
./A  9.65s user 0.12s system 99% cpu 9.768 total

لذلك العثور على أفضل مولد prime. :-)

أخيرا، هناك مكتبة حول اختراق للمولدات السريعة Prime:

http://hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/data-numbers-primes.html.

باستخدامه، يصبح وقتنا:

$ cabal install primes
$ cabal install stream-fusion

$ cat A.hs
import qualified Data.List.Stream as S
import Data.Numbers.Primes

main = print . S.sum . S.takeWhile (<= 2000000) $ primes

$ ghc -O2 -fvia-C -optc-O3 A.hs --make

$ time ./A
142913828922
./A  0.62s user 0.07s system 99% cpu 0.694 total

Answer 3

كتبت "غربال eratosthenes" هنا:

import Data.List
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

باستخدام هذا، يستغرق حوالي 25s إلى print . sum $ takeWhile (<= 20000000) على سطح المكتب. يمكن ان يكون افضل؟ بالتأكيد، يستغرق ج أقل من 1 ثانية لتشغيل

 + / / P: IP: ^: _ 1] 20000000 12272577818052

ولكن لديها مولد الأرقام الأول الأمثل جدا.

Answer 4

الجزء البطيء من وظيفتك هو بالتأكيد توليد الأعداد الأولية وليس sum وظيفة. وسوف تكون طريقة لطيفة لتوليد الأعداد الأولية:

isprime :: (Integral i) => i -> Bool
isprime n = isprime_ n primes
  where isprime_ n (p:ps)
          | p*p > n        = True
          | n `mod` p == 0 = False
          | otherwise      = isprime_ n ps

primes :: (Integral i) => [i]
primes = 2 : filter isprime [3,5..]

أعتقد أنه قابل للقراءة للغاية، رغم أنه من المستغرب بعض الشيء أنه يعمل على الإطلاق لأنه يستخدم الإصابة والكسل primes قائمة. إنه أيضا سريع إلى حد ما، على الرغم من أن المرء يمكن أن يفعل المزيد من التحسينات على حساب قابلية القراءة.