F# 中不可变集和映射的样式是什么

Question

我刚刚解决了 Project Euler 中的 problem23 ，其中我需要一个设置来存储所有丰富的数字。 F# 有一个不可变的集合，我可以使用 Set.empty.Add(i) 创建一个包含数字 i 的新集合。但我不知道如何使用不可变集来做更复杂的事情。

例如，在下面的代码中，我需要看看数字“x”是否可以写成一组中两个数字的和。我求助于排序数组和数组的二分搜索算法来完成工作。

还请评论我以下节目的风格。谢谢！

let problem23 = 
    let factorSum x =
        let mutable sum = 0
        for i=1 to x/2 do
            if x%i=0 then
                sum <- sum + i
        sum
    let isAbundant x = x < (factorSum x)
    let abuns = {1..28123} |> Seq.filter isAbundant |> Seq.toArray
    let inAbuns x = Array.BinarySearch(abuns, x) >= 0
    let sumable x = 
        abuns |> Seq.exists (fun a -> inAbuns (x-a))
    {1..28123} |> Seq.filter (fun x -> not (sumable x)) |> Seq.sum

更新后的版本：

let problem23b =
    let factorSum x =
        {1..x/2} |> Seq.filter (fun i->x%i=0) |> Seq.sum
    let isAbundant x = x < (factorSum x)
    let abuns = Set( {1..28123} |> Seq.filter isAbundant )
    let inAbuns x = Set.contains x abuns  
    let sumable x = 
        abuns |> Seq.exists (fun a -> inAbuns (x-a))
    {1..28123} |> Seq.filter (fun x -> not (sumable x)) |> Seq.sum

这个版本运行了大约27秒，而前23秒（我运行了好几次）。因此，与使用二分搜索的排序数组相比，不可变的红黑树实际上并没有降低太多速度。集合/数组中的元素总数为 6965。

Answer 1

你的风格很适合我。算法中的不同步骤是清晰的，这是使某些东西发挥作用的最重要的部分。这也是我用来解决欧拉计划问题的策略。首先使其工作，然后使其快速。

正如已经说过的，用 Set.contains 替换 Array.BinarySearch 使代码更具可读性。我发现在我编写的几乎所有 PE 解决方案中，我只使用数组进行查找。我发现在 F# 中使用序列和列表作为数据结构更加自然。一旦你习惯了它们，就是这样。

我不认为在函数内部使用可变性一定是坏事。我通过一些积极的可变性优化将问题 155 从近 3 分钟缩短到 7 秒。一般来说，我会将其保存为优化步骤，并开始使用折叠/过滤器等来编写它。在问题 155 的示例中，我确实开始使用不可变函数组合，因为它进行了测试，最重要的是，理解，我的做法很简单。

选择错误的算法比首先使用速度稍慢的不可变方法对解决方案的危害要大得多。一个好的算法即使比可变版本慢，仍然很快（沙发你好队长明显！咳嗽）。

编辑：让我们看看您的版本

您的 Problem23b() 在我的电脑上花了 31 秒。

优化1：使用新算法。

//useful optimization: if m divides n, (n/m) divides n also
//you now only have to check m up to sqrt(n)
let factorSum2 n = 
    let rec aux acc m =
        match m with
        | m when m*m = n -> acc + m
        | m when m*m > n -> acc
        | m -> aux (acc + (if n%m=0 then m + n/m else 0)) (m+1)
    aux 1 2

这仍然非常符合函数式风格，但在代码中使用更新后的 FactorSum，执行时间从 31 秒缩短到 8 秒。

一切仍然是不可变的风格，但让我们看看使用数组查找而不是集合时会发生什么：

优化 2：使用数组进行查找：

let absums() = 
    //create abundant numbers as an array for (very) fast lookup
    let abnums = [|1..28128|] |> Array.filter (fun n -> factorSum2 n > n)
    //create a second lookup: 
    //a boolean array where arr.[x] = true means x is a sum of two abundant numbers
    let arr = Array.zeroCreate 28124
    for x in abnums do 
        for y in abnums do
            if x+y<=28123 then arr.[x+y] <- true
    arr

let euler023() = 
    absums() //the array lookup
    |> Seq.mapi (fun i isAbsum -> if isAbsum then 0 else i) //mapi: i is the position in the sequence
    |> Seq.sum

//I always write a test once I've solved a problem.
//In this way, I can easily see if changes to the code breaks stuff.
let test() = euler023() = 4179871 

执行时间：0.22 秒（！）。

这就是我非常喜欢 F# 的原因，它仍然允许您使用可变结构来修补算法的底层。但我仍然只是在先完成一些更优雅的工作之后才这样做。

Answer 2

您可以根据给定的值序列轻松创建Set。

let abuns = Set (seq {1..28123} |> Seq.filter isAbundant)

因此，inAbuns 将被重写为

let inAbuns x = abuns |> Set.mem x

Seq.exists 将更改为 Set.exists

但数组实现也很好......

请注意，有不需要在 factorSum 中使用可变值，除了它是不正确的，因为您计算的是除数的数量而不是它们的总和：

let factorSum x = seq { 1..x/2 } |> Seq.filter (fun i -> x % i = 0) |> Seq.sum

Answer 3

这是一个简单的功能解决方案，它比原来的更短，速度快了 100 倍以上：

let problem23 =
  let rec isAbundant i t x =
    if i > x/2 then x < t else
      if x % i = 0 then isAbundant (i+1) (t+i) x else
        isAbundant (i+1) t x
  let xs = Array.Parallel.init 28124 (isAbundant 1 0)
  let ys = Array.mapi (fun i b -> if b then Some i else None) xs |> Array.choose id
  let f x a = x-a < 0 || not xs.[x-a]
  Array.init 28124 (fun x -> if Array.forall (f x) ys then x else 0)
  |> Seq.sum

第一个技巧是记录在由数字本身索引的数组中哪些数字丰富，而不是使用搜索结构。第二个技巧是注意所有时间都花在生成该数组上，因此要并行执行。