F # правильно использует кеш последовательностей - PullRequest
Новая
       17

F # правильно использует кеш последовательностей

9 голосов
/ 30 июня 2009

Я пытаюсь использовать Seq.cache с созданной мной функцией, которая возвращает последовательность простых чисел до числа N, исключая число 1. У меня возникают проблемы с выяснением, как сохранить кэшированную последовательность в области видимости, но все еще использую это в моем определении. 

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, чтобы сделать это быстрее? В настоящее время он продолжает падать из области видимости и только снижает производительность.

Ответы [ 3 ]

10 голосов
/ 30 июня 2009

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

Я не сравнивал эффективность этого метода с вашими.

2 голосов
/ 01 июля 2009

Вы смотрели на LazyList? Похоже, он предназначен для решения той же проблемы. Это в PowerPack.

2 голосов
/ 30 июня 2009

Я разобрался, как решить свою проблему со сгибом, но не думал об использовании 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]
...