欧拉23日在C＃0.2秒，在F＃30.5秒。为什么？ [英] Euler 23 in C#: 0.2 seconds, in F#: 30.5 seconds. Why?
问题描述
我不很满意我的F＃的解决了这个问题，因为我无法找到一个美丽的&安培;快速的解决方案，但是这不是这里的问题。问题是，我翻译的解决方案，以C＃为它赫克，这是快速的。像，真快，相比较。
我想不通为什么。是的，我去过反射器，C＃代码看起来非常相似，不能说我真正了解IL，但它看起来有点像一样。我能想到的唯一的事情就是F＃INT的性能[]对C＃列表
所以这里有云：
F＃
模块Euler023
让divisorsSum N =
让可变的总和=在[2..limit]做
如果n％I = 0再总结及下1
设上限=（INT（开方（浮点N）））
为I; - 总和+ I + N / I
如果（限制*限）= N再总结限制其他款项
让isAbundant X =（divisorsSum X）> X
让abundants = [1 ..28123] |> List.filter isAbundant |> List.toArray
让利域= System.Collections.BitArray（28124）
让REC loopUntil IJ =
如果我= abundants.Length则（）
ELIFĴ = abundants.Length然后loopUntil第（i + 1）第（i + 1）
，否则
让总和= abundants [I] + abundants [j]的
如果总和与所述; 28124然后
domain.Set（总和，真）
loopUntil我第（j + 1）
，否则
loopUntil第（i + 1）第（i + 1）
设解决= loopUntil 0 0
[1..28123] |> List.filter（好玩点¯x - > domain.Get（X）= FALSE）|> List.sum
C＃
静态INT divisorsSum（INT N）
{
INT总和= 0;
VAR限额=（INT）的Math.sqrt（N）;
的for（int i = 2; I< =限制; ++ i）如（N％我== 0）之和+ = I + N / I;
如果（（*上限限制）== n）的总和回报限;
返回总和;
}
静态列表< INT> getAbundants（INT上限）
{
变种RET =新的List< INT>（）;
的for（int i = 1; I<上限; ++ i）如（divisorsSum（I）I标记）ret.Add（I）
返回RET;
}
静态无效的主要（字串[] args）
{
VAR abundants = getAbundants（28124）;
变种BITFIELD =新布尔[28124]
的for（int i = 0; I< abundants.Count ++ I）
为（INT J =; J< abundants.Count ++ j）条
{
VAR总和= abundants [I] + abundants [J]。
如果（总和< 28124）BITFIELD [总和] =真;
，否则突破;
}
无功总= 0;
的for（int i = 0; I< 28124; ++ i）如（位域[I] ==假）总+ =我;
}
更新
包含此代码的项目包括每个问题（EulerXXX.fs）+主程序文件一个单独的文件中。主程序文件如下：
模块程序=
让秒表=系统。 Diagnostics.Stopwatch（）
让可变TOTALTIME = System.TimeSpan（）
让行内打勾（）
=
stopWatch.Stop（）;
TOTALTIME< - totalTime.Add stopWatch.Elapsed
printfn - >消逝：2.2F％合计秒：％2.2fsstopWatch.Elapsed.TotalSeconds totalTime.TotalSeconds
stopWatch.Restart （）
让_ =
stopWatch.Start（）
printf的Euler001解决方案：％AEuler001.solve
打勾（）
printf的Euler002解决方案：％AEuler002.solve
打勾（）
printf的Euler003解决方案：％AEuler003.solve
打勾（）
printf的Euler004解决方案：％AEuler004.solve
打勾（）
printf的Euler005解决方案：％AEuler005.solve
打勾（）
printf的Euler006解决方案：％AEuler006。解决
打勾（）
printf的Euler007解决方案：％AEuler007.solve
打勾（）
printf的Euler008解决方案：％AEuler008.solve
剔（）
printf的Euler009解决方案：％AEuler009.solve
打勾（）
printf的Euler010解决方案：％AEuler010.solve
打勾（）
printf的Euler011解决方案：％AEuler011.solve
打勾（）
printf的Euler012解决方案：％AEuler012.solve
打勾（）
printf的Euler013解决方案：％ AEuler013.solve
打勾（）
printf的Euler014解决方案：％AEuler014.solve
打勾（）
printf的Euler015解决方案：％AEuler015.solve
打勾（）
printf的Euler016解决方案：％AEuler016.solve
打勾（）
printf的Euler017解决方案：％AEuler017.solve
打勾（）
printf的Euler018解决方案：％AEuler018.solve
打勾（）
printf的Euler019解决方案：％AEuler019.solve
打勾（）
的printf Euler020解决方案：％AEuler020.solve
打勾（）
printf的Euler021解决方案：％AEuler021.solve
打勾（）
printf的Euler022解决方案：％A Euler022.solve
打勾（）
printf的Euler023解决方案：％AEuler023.solve
打勾（）
printf的Euler024解决方案：％AEuler024.solve
打勾（）
printf的Euler059解决方案：％AEuler059.solve
打勾（）
printf的Euler067解决方案：％AEuler067.solve
打勾（）
stopWatch.Stop（）
System.Console.ReadLine（）
的输出程序如下：
Euler001解决方案：233168 - >经过：0.02秒总计：0.02秒
Euler002解决方案：4613732 - >经过：0.03秒总计：0.04小号
...
Euler022解决方案：871198282 - >经过：0.02秒总计：4.11小号
Euler023解决方案：4179871 - >经过：81.11秒总计：85.22小号
Euler024解决方案：2; 7; 8; 3; 9; 1; 5; 4; 6; 0] - GT;经过：0.01秒总计：85.23小号
...
Euler067解决方案：[7273] - >经过：0.01秒总计：85.31小号
所以，问题不是出在项目参数。另外，如果我从Euler023复制代码为程序就会立即运行。
现在的问题是，为什么会发生这种放缓只是对这个问题发生？
您F＃的版本是不慢在所有;它需要在F＃互动0.44秒我的机器上。我不知道你怎么可以观察这种缓慢（30.5秒）。如果你编译并运行代码，请确保你在释放模式并且启动优化和尾部调用消除。
不过，你仍然可以进一步消除优化使用冗余的中间集合。
一个。变化（冗余）名单 [2..limit] 来范围
<预类=郎毫升prettyprint-覆盖>
因为我在做2..limit
如果N％I = 0再总结< - 总和+ 1 + N / I
B.生成abundants的阵列，而无需创建大名单（更忠实于C＃版本）：
<预类=郎毫升prettyprint-覆盖>
让abundants =
让ARR = ResizeArray（28123）在1..28123
为我做
如果isAbundant我再arr.Add我
arr.ToArray（）
℃。计算解决，而无需创建大名单：
<预类=郎毫升prettyprint-覆盖>
让解决=
loopUntil 0 0
让可变的总和= 0
，因为我在做1..28123
如果不是< | domain.Get（我），然后
总和< - 总和+ I
总和
新的F＃版本比原来的4倍速度更快; 。它需要大约0.1秒就可以完成。
更新：
您测量不准确的。首先，你测得的印刷值的两个电话之间的时间差。其次， EulerXXX.solve 是值;所以他们预先计算的，当你编译你的程序。你应该申报 EulerXXX.solve 的功能：
<预类=郎毫升prettyprint-覆盖>
让解决（）= ...
和衡量执行时间的函数调用：
<预类=郎毫升prettyprint-覆盖>
让时间FN =
让SW =新System.Diagnostics.Stopwatch（）
sw.Start（）
让F = FN（）
sw.Stop（）
printfn所用时间：％.2f的< | （浮动sw.ElapsedMilliseconds）/1000.0
F
让S023 =时间Euler023.solve
printf的Euler023解决方案：％AS023
I am not really satisfied with my F# solution to this problem because I can't find a beautiful & fast solution, but that's not the issue here. The issue is, I translated the solution to C# for the heck of it, and it is fast. Like, really fast, comparatively.
I can't figure out why. Yes, I've been to Reflector, C# code looks very similar, can't say I really understand IL but it looks kinda like the same. The only thing I can think of is performance of F# int[] against C# List.
So here it goes:
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;
}
Update
The project containing this code consists of a separate file for each problem (EulerXXX.fs) + the main program file. Main program file is as follows
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()
The output of the program is as follows:
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
So the problem is not in project parameters. Also, if I copy code from Euler023 to Program it will run instantly. The question is, why does this slowdown happen only for this problem?
Your F# version isn't slow at all; it takes 0.44 seconds in F# Interactive on my machine. I don't know how you could observe such a slowness (30.5 seconds). If you compile and run the code, make sure that you're in Release mode and turning on optimization and tail call elimination.
However, you still can optimize further by eliminating the use of redundant intermediate collections.
A. Change (redundant) list [2..limit] to range expression 2..limit in divisorsSum:
for i in 2..limit do
if n%i=0 then sum <- sum+i+n/i
B. Generate array of abundants without creating the big list (more faithful to C# version):
let abundants =
let arr = ResizeArray(28123)
for i in 1..28123 do
if isAbundant i then arr.Add i
arr.ToArray()
C. Calculate solve without creating the big list:
let solve =
loopUntil 0 0
let mutable sum = 0
for i in 1..28123 do
if not <| domain.Get(i) then
sum <- sum + i
sum
The new F# version is 4x faster than the original one; it takes about 0.1 seconds to complete.
UPDATE:
Your measurement is inaccurate. First, you measured time difference between two calls of printing values. Second, EulerXXX.solve are values; so they are pre-calculated when you compiled your program. You should declare EulerXXX.solve as functions:
let solve() = ...
and measure execution time of function calls:
let time fn =
let sw = new System.Diagnostics.Stopwatch()
sw.Start()
let f = fn()
sw.Stop()
printfn "Time taken: %.2f s" <| (float sw.ElapsedMilliseconds)/1000.0
f
let s023 = time Euler023.solve
printf "Euler023 solution: %A" s023
这篇关于欧拉23日在C＃0.2秒，在F＃30.5秒。为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
