하스켈 : 소수

Question

의 빠른 요약

면책 조항 : 나는 꽤 많은 수를 추가 해요 9

, 모든 소수 1 ~ 2 000 000

그 합산에 오일러 문제에 일하고 있어요 소수는 영원히 걸립니다. 함수 'sum'에 내장 된 haskell을 사용하고 있습니다.

sum listOfPrimes 

는 다른 빠른 옵션이 있습니다

같이?

- 내 소수 생성자가 내 코드에서 느린 링크였습니다.

Answer 1

숫자를 요약하는 것이 아니라 생성하는 것이 문제인 것 같습니다. listOfPrimes의 구현은 무엇입니까?

이 논문은 관심을 가질 : http://lambda-the-ultimate.org/node/3127

Answer 2

내가 here는 "에라토스테네스의 체"쓴이 사용

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 

을, 내 바탕 화면에 print . sum $ takeWhile (<= 20000000)에 25 초 정도 걸립니다. 더 좋을까요? 물론, 그것은

 
    +/p:i.p:^:_1]20000000 
12272577818052 

을 실행하는 J 제 1 항에 따라 필요하지만 그것은 매우 최적화 된 소수 생성기가 있습니다.

Answer 3

ghci가 아닌 ghc -O2를 사용하고 싶습니까? 당신 문제는 합계가 아니라 세대에있을 것입니다.

가장 빠른 방법 중 하나는 스트림 융합 기반 시퀀스를 사용하는 것이 가장 좋습니다.

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 

는 스트림으로 전환, 그래서 합계 : 일반 목록으로. 마지막으로 합을 대체

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

,

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

는 몇 가지 작은 시간을 절약 그러나 우리는 모두 요약을 폐기하면 우리가 볼 수있는 문제는, 소수 생성 될 것입니다 : takeWhile는 퓨즈

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

더 나은 소수 생성자를 찾으십시오. :-)

마지막으로, 빠른 주요 발전기 Hackage에 라이브러리있다 :

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 4

함수의 느린 부분입니다 확실히 sum 함수가 아닌 소수 생성.좋은 방법은 소수가 될 것이다 생성 : 그것은 primes 목록의 재귀와 게으름을 사용하기 때문에 전혀 작동 어쩌면 조금 의외이지만

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..] 

나는 매우 읽을 생각합니다. 가독성을 희생하여 추가 최적화를 수행 할 수 있지만 다소 빠릅니다.