F # 시퀀스 캐쉬를 올바르게 사용함.

Question

숫자 1을 제외한 숫자 N까지 소수의 시퀀스를 반환하는 함수로 Seq.cache를 사용하려고합니다. 캐시 된 시퀀스는 범위에 있지만 여전히 내 정의에서 사용합니다.

let rec primesNot1 n = 
    {2 .. n} 
    |> Seq.filter (fun i -> 
     (primesNot1 (i/2) |> Seq.for_all (fun o -> i % o <> 0))) 
    |> Seq.append {2 .. 2} 
    |> Seq.cache 

Seq.cache를 사용하여 더 빠르게 만들 수있는 아이디어는 무엇입니까? 현재 범위를 벗어나지 만 성능이 저하됩니다.

Answer 1

Seq.cache 캐시는 IEnumerable<T> 인스턴스를 캐시하므로 시퀀스의 각 항목은 한 번만 계산됩니다. 귀하의 경우에는 함수에 의해 반환 된 시퀀스를 캐싱하고 있으며 함수를 호출 할 때마다 캐시 된 시퀀스가 ​​생겨 어떤 좋은 결과도 얻지 못합니다. 나는 캐싱이 당신의 문제에 대한 올바른 접근 방식이라고 생각하지 않는다. 대신 당신은 아마도 메모를보아야합니다.

n보다 작은 소수를주는 함수를 정의하는 대신 무한한 열거 가능한 소수의 시퀀스를 정의하려는 경우 캐싱이 더 적합합니다. 그러면 다음과 같이 보일 것입니다.

let rec upFrom i = 
    seq { 
    yield i 
    yield! upFrom (i+1) 
    } 

let rec primes = 
    seq { 
    yield 2 
    yield! 
     upFrom 3 |> 
     Seq.filter (fun p -> primes |> Seq.takeWhile (fun j -> j*j <= p) |> Seq.forall (fun j -> p % j <> 0)) 
    } 
    |> Seq.cache 

나는이 방법의 성능을 자신의 것과 비교하지 않았습니다.

Answer 2

폴드로 내 문제를 해결하는 방법을 알아 냈지만 seq.cache를 사용하는 것은 아닙니다.

let primesNot1 n = 
    {2 .. n} 
    |> Seq.fold (fun primes i -> 
     if primes |> Seq.for_all (fun o -> i % o <> 0) then 
      List.append primes [i] 
     else 
      primes) [2] 

Answer 3

LazyList를 살펴 보셨습니까? 동일한 문제를 해결하도록 설계된 것처럼 보입니다. PowerPack에 있습니다.