Haskell 스타일/효율성

StackOverflow https://stackoverflow.com/questions/897525

문제

그래서 나는 Primes를 게으르게 생성하는 방법을 찾고 있었고, 나는이 세 가지 정의를 생각해 냈습니다.이 세 가지 정의는 모두 동등한 방식으로 작동합니다. 각각의 새 정수가 앞의 모든 프라임 중 요인이 있는지 확인합니다.

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) 모든 정수에 대해 (I. 생각한다 지금까지 찾은 프라임 수의 순서에 대한 작업이 필요하며 새로운 프라임이 발생할 때만 업데이트됩니다.

비과학적인 테스트 (실행 take 1000 GHCI에서)처럼 보인다 primes3 보다 빨리 실행됩니다 primes2.

이것으로부터 교훈을 얻어야하고, 배열에서의 작업으로 함수를 나타낼 수 있다면, 효율성을 위해 후자의 방식으로 구현해야한다고 가정해야합니까, 아니면 다른 일이 일어나고 있습니까?

도움이 되었습니까?

해결책

두 번째 논쟁은 무엇입니까 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! 정수 곱셈, 분할 및 계수는 정수 첨가 및 뺄셈보다 훨씬 느립니다. 내 컴퓨터 에서이 구현은 처음 1000 프라임 (GHC 6.10.3)을 계산할 때 40% 더 빠른 시계를 기록합니다. -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]}
...

지도는 추가 외에는 미래의 배수를 추적합니다.

다른 팁

주목하십시오 primes3 변경하여보다 효율적으로 만들 수 있습니다 ps++[x] 에게 (x:ps). 달리기 (++) 왼쪽 인수의 길이는 선형이지만 오른쪽 인수의 길이는 일정합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top