F#:低效的序列处理

Question

我有以下代码在 F# 中执行埃拉托色尼筛法:

let sieveOutPrime p numbers =
   numbers
   |> Seq.filter (fun n -> n % p <> 0)

let primesLessThan n =
    let removeFirstPrime = function
       | s when Seq.isEmpty s -> None
       | s -> Some(Seq.head s, sieveOutPrime (Seq.head s) (Seq.tail s))

    let remainingPrimes =
       seq {3..2..n}
       |> Seq.unfold removeFirstPrime

    seq { yield 2; yield! remainingPrimes }

当 primesLessThan 的输入非常大时，这会非常慢:primes 1000000 |> Seq.skip 1000;; 我花了将近一分钟，尽管 primes 1000000 本身自然非常快，因为它只是一个序列。

我做了一些尝试，我认为罪魁祸首一定是 Seq.tail(在我的 removeFirstPrime 中)正在做一些密集的事情。 According to the docs ，它正在生成一个全新的序列，我可以想象它很慢。

如果这是 Python 并且序列对象是一个生成器，那么确保此时没有任何昂贵的事情发生将是微不足道的:只是 yield 从序列中，我们已经廉价地删除了它的第一个元素。

F# 中的

LazyList doesn't seem拥有 unfold 方法(或者，就此而言，filter 方法)；否则我认为 LazyList 会是我想要的东西。

如何通过防止不必要的重复/重新计算来加快此实现？理想情况下，无论 n 有多大，primesLessThan n |> Seq.skip 1000 都将花费相同的时间。

Answer 1

递归解决方案和序列不能很好地结合在一起(比较答案 here ，它与您使用的模式非常相似)。您可能想检查生成的代码，但我认为这是一个经验法则。

LazyList(在 FSharpX 中定义)当然带有 unfold和过滤器定义，如果没有定义，那就太奇怪了。通常在 F# 代码中，这种功能在单独的模块中提供，而不是作为类型本身的实例成员提供，这种约定似乎确实混淆了大多数文档系统。