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，我们已经很便宜了丢弃了它的第一个元素。

LazyList 在 F# doesn't seem 中使用 unfold 方法（或者，就此而言，filter 方法）；否则我认为 LazyList 会是我想要的东西。

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

Answer 1

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

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

Answer 2

您可能知道 Seq 是一个惰性求值集合。 Sieve 算法是关于从序列中过滤掉 non-primes，这样你就不必再考虑它们了。

但是，当您将 Sieve 与延迟评估的集合结合使用时，您最终会一遍又一遍地过滤相同的 non-primes。

如果从 Seq 切换到 Array 或 List，您会看到更好的性能，因为这些集合的 non-lazy 方面意味着您只过滤 non-primes一次。

提高代码性能的一种方法是引入缓存。

let removeFirstPrime s =
   let s = s |> Seq.cache 
   match s with
   | s when Seq.isEmpty s -> None
   | s -> Some(Seq.head s, sieveOutPrime (Seq.head s) (Seq.tail s))

我实现了一个与 Seq 非常相似的 LazyList，它允许我计算评估的数量：

对于 2000 以内的所有素数。

无缓存：14753706 次评估
使用缓存：97260 次评估

当然，如果你真的需要性能，你可以使用可变数组实现。

PS。性能指标

Running 'seq' ...
  it took 271 ms with cc (16, 4, 0), the result is: 1013507
Running 'list' ...
  it took 14 ms with cc (16, 0, 0), the result is: 1013507
Running 'array' ...
  it took 14 ms with cc (10, 0, 0), the result is: 1013507
Running 'mutable' ...
  it took 0 ms with cc (0, 0, 0), the result is: 1013507

这是 Seq 缓存。 F# 中的 Seq 开销相当高，Seq 有一些有趣的惰性替代方法，例如 Nessos。

List 和 Array 运行大致相似，但由于更紧凑的内存布局，GC 指标更适合 Array（Array 的 10 cc0 集合与 16列表的 cc0 集合）。 Seq 的 GC 指标更差，因为它强制执行 4 次 cc1 回收。

筛选算法的可变实现具有更好的内存和性能指标。

F#：低效的序列处理

F#: inefficient sequence processing

primes

f#

sequence

lazy-evaluation

sieve-of-eratosthenes