F#中不可变集合和映射的风格是什么？

Question

我刚刚在欧拉计划中解决了problem23问题，其中需要使用set来存储所有过剩数。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。

- Yin Zhu

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#的原因，它仍然允许您使用可变结构来调整算法。但在我让更优雅的东西先运行之后，我才会这样做。

- cfern

---

不错！可以用位数组替换数组以节省一些空间。 :) - Yin Zhu

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

- Dario

---

注意：在最新版本的 F# 中，Set.mem 已被替换为 Set.contains。 - cfern

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

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

- J D