하스켈 스타일/효율성

Question

그래서 나는 소수를 지연 생성하는 방법을 연구하고 있었고,이 모든 세 가지 정의를 생각해 냈습니다.이 세 정의는 모두 같은 방식으로 작동합니다. 각각의 새로운 정수가 이전의 소수 : 그것은 소수의 수 의 순서에 작업이 필요합니다 내가 생각 모든 정수 (대한 f_ = f (const True)을 재 계산 피할 수 있기 때문에

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보다 약간 더 빠르게 처리 될 우리 지금까지 찾은 것), enc 할 때만 업데이트합니다. 새 총리를 기른다.

그냥 비 과학적 테스트에서 (ghci에서 take 1000를 실행)는 primes3 빠르게 실행 primes2 이상처럼 보인다.

나는이에서 교훈을, 그리고 내가 배열에 대한 작업 같은 기능을 나타낼 수 있다면, 내가 효율성 후자의 방식을 구현해야한다고 가정, 또는 뭔가 다른 여기에 무슨이해야 ?

Answer 1

f의 두 번째 인수는 무엇입니까? 제 생각에는, 이러한 대안을 모두 다시 질문에,

---

어쨌든 ... 더 읽을 수 있으며, 성능에 큰 영향을주지 않습니다. 때로는 함수를 데이터 구조로 사용하는 것이 특정 작업을 가장 잘 표현하는 경우가 있으며 때로는 그렇지 않은 경우도 있습니다. 코딩의 용이함과 성능 측면에서의 "최고"라는면에서 "최고"는 항상 같은 것은 아닙니다. 은 "기능 데이터 구조로"기술은 runtime compilation에 필수적이지만, 해당 페이지는 경고로,

는

런타임 컴파일은 때때로 당신에게 상당한 효율성 향상을 이길 수 있지만, 종종 당신의 증가 스트레스의 비용으로 거의 아무것도 이길 수 없다 생산성 감소. 귀하의 경우에는

는 각 f :: Integer -> ... -> Bool을 구성하는 오버 헤드가 all ... ps 대 f ... x를 호출 할 때 거의 또는 전혀 차이가 각 ps :: [Integer]을, 건설의 오버 헤드보다 훨씬 더 높은 가능성이 높습니다.

---

무한 소수 체에서 사이클을 짜려면 mod에 호출 없애 버려! 정수 곱셈, 나눗셈 및 모듈러스는 정수 덧셈 및 뺄셈보다 훨씬 느립니다. 내 컴퓨터에서이 구현은 처음 1000 소수 (GHC 6.10.3 -O2)를 계산할 때 40 % 빨라집니다. (JSON 틱 구문의 비트를 사용하여) 액션에서

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 

,

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

은 ps++[x]을 (x:ps)으로 변경하면 더 효율적으로 만들 수 있습니다.실행중인 (++)은 왼쪽 인수의 길이는 선형이지만 오른쪽 인수의 길이는 일정합니다.