F # utilisant le cache de séquence correctement

Question

J'essaie d'utiliser Seq.cache avec une fonction que j'ai faite qui retourne une séquence de nombres premiers jusqu'à un nombre N à l'exclusion du nombre 1. Je n'arrive pas à comprendre comment garder le cache de séquence séquence mise en cache dans la portée, mais toujours l'utiliser dans ma définition.

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 

Des idées sur la façon dont je pourrais utiliser Seq.cache pour accélérer les choses? Actuellement, il ne cesse de perdre de sa portée et ne fait que ralentir les performances.

Answer 1

Seq.cache met en cache une instance IEnumerable<T> afin que chaque élément de la séquence soit calculé une seule fois. Dans votre cas, cependant, vous mettez en cache la séquence renvoyée par une fonction, et chaque fois que vous appelez la fonction, vous obtenez une nouvelle séquence en mémoire cache, ce qui ne vous convient pas du tout. Je ne pense pas que la mise en cache soit vraiment la bonne approche de votre problème, comme vous l'avez souligné; Au lieu de cela, vous devriez probablement vous pencher sur la mémo. Si au lieu de définir une fonction donnant les nombres premiers inférieurs à n vous voulez définir une séquence infinie de nombres premiers, alors la mise en cache est plus logique. Cela ressemblerait plus à ceci:

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 

Je n'ai pas comparé les performances de cette méthode par rapport aux vôtres.

Answer 2

J'ai trouvé comment résoudre mon problème avec un pli mais pas mon idée d'utiliser 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

Avez-vous regardé LazyList? On dirait que c'est conçu pour résoudre le même problème. C'est dans PowerPack.