我对我对这个问题的 F# 解决方案不是很满意,因为我找不到漂亮且快速的解决方案,但这不是这里的问题。问题是,我把解决方案翻译成 C# 真是太棒了,而且速度很快。就像,真的很快,相对而言。
我不知道为什么。是的,我去过Reflector,C#代码看起来很相似,不能说我真的了解IL,但看起来有点像。我唯一能想到的是 F# int[] 对 C# List 的性能。
所以这里是:
F#
module Euler023
let divisorsSum n =
let mutable sum = 1
let limit = (int (sqrt(float n)))
for i in [2..limit] do
if n%i=0 then sum <- sum+i+n/i
if (limit*limit)=n then sum-limit else sum
let isAbundant x = (divisorsSum x)>x
let abundants = [1..28123] |> List.filter isAbundant |> List.toArray
let domain = System.Collections.BitArray(28124)
let rec loopUntil i j =
if i=abundants.Length then ()
elif j=abundants.Length then loopUntil (i+1) (i+1)
else
let sum = abundants.[i]+abundants.[j]
if sum<28124 then
domain.Set(sum, true)
loopUntil i (j+1)
else
loopUntil (i+1) (i+1)
let solve = loopUntil 0 0
[1..28123] |> List.filter (fun x -> domain.Get(x)=false) |> List.sum
C#
static int divisorsSum(int n)
{
int sum = 0;
var limit = (int)Math.Sqrt(n);
for (int i=2;i<=limit;++i) if (n%i==0) sum += i + n/i;
if ((limit * limit) == n) return sum-limit;
return sum;
}
static List<int> getAbundants(int ceiling)
{
var ret = new List<int>();
for (int i = 1; i < ceiling; ++i) if (divisorsSum(i) > i) ret.Add(i);
return ret;
}
static void Main(string[] args)
{
var abundants = getAbundants(28124);
var bitField = new bool[28124];
for (int i = 0; i < abundants.Count; ++i)
for (int j = i; j < abundants.Count; ++j)
{
var sum = abundants[i] + abundants[j];
if (sum < 28124) bitField[sum] = true;
else break;
}
var total = 0;
for (int i = 0; i < 28124; ++i) if (bitField[i]==false) total += i;
}
更新
包含此代码的项目由每个问题的单独文件 (EulerXXX.fs) + 主程序文件组成。主程序文件如下
module Program =
let stopWatch = System.Diagnostics.Stopwatch()
let mutable totalTime = System.TimeSpan()
let inline tick()
=
stopWatch.Stop();
totalTime <- totalTime.Add stopWatch.Elapsed
printfn " -> Elapsed: %2.2f sec Total: %2.2f s" stopWatch.Elapsed.TotalSeconds totalTime.TotalSeconds
stopWatch.Restart()
let _ =
stopWatch.Start()
printf "Euler001 solution: %A" Euler001.solve
tick()
printf "Euler002 solution: %A" Euler002.solve
tick()
printf "Euler003 solution: %A" Euler003.solve
tick()
printf "Euler004 solution: %A" Euler004.solve
tick()
printf "Euler005 solution: %A" Euler005.solve
tick()
printf "Euler006 solution: %A" Euler006.solve
tick()
printf "Euler007 solution: %A" Euler007.solve
tick()
printf "Euler008 solution: %A" Euler008.solve
tick()
printf "Euler009 solution: %A" Euler009.solve
tick()
printf "Euler010 solution: %A" Euler010.solve
tick()
printf "Euler011 solution: %A" Euler011.solve
tick()
printf "Euler012 solution: %A" Euler012.solve
tick()
printf "Euler013 solution: %A" Euler013.solve
tick()
printf "Euler014 solution: %A" Euler014.solve
tick()
printf "Euler015 solution: %A" Euler015.solve
tick()
printf "Euler016 solution: %A" Euler016.solve
tick()
printf "Euler017 solution: %A" Euler017.solve
tick()
printf "Euler018 solution: %A" Euler018.solve
tick()
printf "Euler019 solution: %A" Euler019.solve
tick()
printf "Euler020 solution: %A" Euler020.solve
tick()
printf "Euler021 solution: %A" Euler021.solve
tick()
printf "Euler022 solution: %A" Euler022.solve
tick()
printf "Euler023 solution: %A" Euler023.solve
tick()
printf "Euler024 solution: %A" Euler024.solve
tick()
printf "Euler059 solution: %A" Euler059.solve
tick()
printf "Euler067 solution: %A" Euler067.solve
tick()
stopWatch.Stop()
System.Console.ReadLine()
程序的输出如下:
Euler001 solution: 233168 -> Elapsed: 0.02 sec Total: 0.02 s
Euler002 solution: 4613732 -> Elapsed: 0.03 sec Total: 0.04 s
...
Euler022 solution: 871198282 -> Elapsed: 0.02 sec Total: 4.11 s
Euler023 solution: 4179871 -> Elapsed: 81.11 sec Total: 85.22 s
Euler024 solution: [2; 7; 8; 3; 9; 1; 5; 4; 6; 0] -> Elapsed: 0.01 sec Total: 85.23 s
...
Euler067 solution: [7273] -> Elapsed: 0.01 sec Total: 85.31 s
所以问题不在于项目参数。此外,如果我将代码从 Euler023 复制到 Program,它将立即运行。问题是,为什么这种减速只发生在这个问题上?