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
。