我有以下代码在 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
从序列中,我们已经廉价地删除了它的第一个元素。
LazyList
doesn't seem拥有 unfold
方法(或者,就此而言,filter
方法);否则我认为 LazyList
会是我想要的东西。
如何通过防止不必要的重复/重新计算来加快此实现?理想情况下,无论 n
有多大,primesLessThan n |> Seq.skip 1000
都将花费相同的时间。
最佳答案
递归解决方案和序列不能很好地结合在一起(比较答案 here ,它与您使用的模式非常相似)。您可能想检查生成的代码,但我认为这是一个经验法则。
LazyList
(在 FSharpX 中定义)当然带有 unfold和过滤器定义,如果没有定义,那就太奇怪了。通常在 F# 代码中,这种功能在单独的模块中提供,而不是作为类型本身的实例成员提供,这种约定似乎确实混淆了大多数文档系统。
关于F#:低效的序列处理,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49219103/