Euler 23 en C #: 0.2 segundos, en F #: 30.5 segundos. ¿Por qué?
No estoy realmente satisfecho con mi solución F # para este problema porque no puedo encontrar una solución bonita y rápida, pero ese no es el problema aquí. El problema es que traduje la solución a C # por completo, y es rápido. Al igual que, muy rápido, comparativamente.
No puedo entender por qué. Sí, he estado en Reflector, el código C # parece muy similar, no puedo decir que realmente entiendo IL pero se parece un poco a lo mismo. Lo único que se me ocurre es el rendimiento de F # int [] contra C # List.
Así que aquí va:
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
DO#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;
}
ActualizarEl proyecto que contiene este código consiste en un archivo separado para cada problema (EulerXXX.fs) + el archivo principal del programa. El archivo principal del programa es el siguiente
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()
La salida del programa es la siguiente:
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
Entonces el problema no está en los parámetros del proyecto. Además, si copio el código de Euler023 al programa, se ejecutará instantáneamente. La pregunta es, ¿por qué esta desaceleración ocurre solo para este problema?