무한한 목록을 사용할 때 실행 속도가 느려짐

Question

나는 머리카락을 되찾기 위해 노력하고 있으며, 무엇이 빠르고 느리게하는지, 그리고 나는 이것에 대해 조금 혼란스러워합니다.

필자는 특정 값까지 소수 목록을 생성하는 함수의 두 가지 구현을 가지고 있습니다. 제 직선 하스켈 위키 오프이다

primesTo :: (Ord a, Num a, Enum a) => a -> [a] 
primesTo m = eratos [2..m] where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m]) 

두번째는 동일하지만 내부적 무한리스트를 사용하여 다음 두 경우

primes2 :: (Ord a, Num a, Enum a) => a -> [a] 
primes2 m = takeWhile (<= m) (eratos [2..]) where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..]) 

마이너스 함수이다 :

minus :: (Ord a) => [a] -> [a] -> [a] 
minus (x:xs) (y:ys) = case (compare x y) of 
      LT -> x : minus xs (y:ys) 
      EQ ->  minus xs  ys 
      GT ->  minus (x:xs) ys 
minus xs _ = xs 

후자의 구현은 이전보다 훨씬 느리고 (~ 100x), 나는 이유를 알지 못합니다. 나는 haskell의 게으른 평가가 그들을 후드 아래에서 꽤 동등하게 만들 것이라고 생각했을 것이다.

이것은 분명히 질문의 목적을 위해 축소 된 테스트 케이스입니다. 실생활에서 최적화는 아무런 문제가되지 않지만 (필자는 왜 그것이 필요한지는 모르겠지만) 나에게 무한한 것을 생성하는 함수 소수 목록은 유한 목록보다 일반적으로 더 유용하지만 작업 속도가 느립니다.

Answer 1

이 minus 단계를 나열 페어를 통해

(xs `minus` [p*p, p*p+p..m]) -- primesTo 
(xs `minus` [p*p, p*p+p..]) -- primes2 

기능 사이에 큰 차이가있어 하나 개의 목록은 끝에 도달하면 종료하는 것이 나에게처럼 보인다. 위의 첫 번째 minus 식에서 후자의 목록을 모두 사용한 경우에는 (m-p*p)/p 단계가 발생합니다. 두 번째 단계에서는 항상 length xs의 순서로 단계를 수행합니다.

무한한 목록으로 인해 의미가있는 최적화가 하나 이상 사용 중지되었습니다.

Answer 2

두 번째 경우에는 하나의 추가 소수를 생성해야한다는 차이점이 있습니다. takeWhile이 정지 할 시간을 알기 전에 m보다 큰 첫 번째 소수를 생성해야합니다.

또한 필터 목록과 배수 목록에서 모두 [..m] 경계는 계산 횟수를 줄이는 데 도움이됩니다. 이 목록들 중 하나가 비게 될 때마다 minus은 secons 절을 통해 즉시 반환하지만 무한의 경우에는 빼기가 첫 번째 경우에 멈추게됩니다. 당신이 primes2 밖으로 takeWhile을 강화하고, 시도보다 일반적인 소수 기능을 얻을 수 있습니다

--this is also slow 
primes3 :: (Ord a, Num a, Enum a) => a -> [a] 
primes3 m = takeWhile (<= m) (eratos [2..m]) where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..]) 

--this fast 
primes4 :: (Ord a, Num a, Enum a) => a -> [a] 
primes4 m = takeWhile (<= m) (eratos [2..]) where 
    eratos []  = [] 
    eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..m])