正しく順序キャッシュを使用しての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を見て撮影したことがありますか？同じ問題を解決するために設計されていますように思えます。これは、パワーパックでいます。