F # usando cache de seqüência corretamente
Pergunta
Eu estou tentando usar Seq.cache com uma função que eu fiz que retorna uma seqüência de números primos até um número N excluindo o número 1. Estou tendo dificuldade para descobrir como manter a seqüência em cache no escopo, mas ainda usá-lo na minha definição.
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
Todas as idéias de como eu poderia usar Seq.cache para fazer isso mais rápido? Atualmente ele mantém caindo de escopo e só está a abrandar o desempenho.
Solução
Seq.cache
armazena uma instância IEnumerable<T>
de modo que cada artigo na sequência é calculada apenas uma vez. No seu caso, porém, você está cache a seqüência retornada por uma função, e cada vez que você chamar a função que você obter um nova sequência em cache, o que não fará nenhum bom. Eu não acho que o cache é realmente a abordagem certa para o seu problema como você esbocei-lo; em vez disso você provavelmente deve olhar para memoization.
Se em vez de definir uma função dando os números primos menos de n
você deseja definir uma seqüência enumerável infinito de primos, então cache faz mais sentido. Isso seria mais parecido com isto:
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
Eu não comparou o desempenho deste método em comparação com o seu.
Outras dicas
Eu descobri como resolver o meu problema com uma dobra, mas não a minha ideia de usar 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]
Você deu uma olhada em LazyList? Parece que é projetado para resolver o mesmo problema. É no PowerPack.