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

Question

我刚刚解决了problem23在 Project Euler 中，我需要一个 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。

Answer 1

我觉得你的风格很好。算法中的不同步骤很清楚，这是使某件事情发挥作用的最重要部分。这也是我用来解决 Project Euler 问题的策略。首先让它工作，然后让它快速。

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

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

选择错误的算法比首先使用速度稍慢的不可变方法更有害于解决方案。一个好的算法仍然很快，即使它比可变版本慢(couch 你好船长很明显!cough)。

编辑:让我们看看你的版本

您的 problem23b() 在我的 PC 上花费了 31 秒。

优化一:使用新算法。

//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# 的地方，它仍然允许您使用可变构造来修补算法的底层。但我仍然只在 我首先做了一些更优雅的工作之后才这样做。