2

この問題に対する私の F# ソリューションには満足していません。なぜなら、美しく高速なソリューションが見つからないからです。しかし、それはここでは問題ではありません。問題は、私がソリューションを C# に翻訳したことです。それは高速です。比較的、本当に速いです。

理由がわかりません。はい、Reflector に行ったことがあります。C# コードは非常によく似ています。IL を本当に理解しているとは言えませんが、同じように見えます。私が考えることができる唯一のことは、C# List に対する F# int[] のパフォーマンスです。

だからここに行く：

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 にコピーすると、すぐに実行されます。問題は、なぜこのスローダウンがこの問題でのみ発生するのかということです。

4

1 に答える 1

6

F＃バージョンはまったく遅くありません。私のマシンのF＃Interactiveでは0.44秒かかります。このような速度低下（30.5秒）をどのように観察できるかわかりません。コードをコンパイルして実行する場合は、リリースモードになっていて、最適化と末尾呼び出しの削除がオンになっていることを確認してください。

ただし、冗長な中間コレクションの使用を排除することで、さらに最適化することができます。

A.（冗長）リスト[2..limit]を次の範囲式に変更2..limitしdivisorsSumます。

for i in 2..limit do
    if n%i=0 then sum <- sum+i+n/i

B.大きなリストを作成せずに豊富な配列を生成します（C＃バージョンにより忠実）：

let abundants = 
    let arr = ResizeArray(28123)
    for i in 1..28123 do
        if isAbundant i then arr.Add i
    arr.ToArray()

C.solve大きなリストを作成せずに計算します。

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

新しいF＃バージョンは、元のバージョンより4倍高速です。完了するまでに約0.1秒かかります。

アップデート：

測定が不正確です。最初に、値を出力する2つの呼び出し間の時間差を測定しました。第二に、EulerXXX.solve値です。したがって、プログラムをコンパイルするときに事前に計算されます。EulerXXX.solve関数として宣言する必要があります。

let solve() = ...

関数呼び出しの実行時間を測定します。

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
于 2012-08-21T07:53:37.477 に答える