F＃末尾再帰とSeqライブラリのパフォーマンスの差

Question

私はこのコードをF＃に入れています。このコードは、1から20までのすべての数字で均等に割り切れる最小の正の数を見つけます。

let isDivisableByAll num (divisors: int[]) = Array.forall (fun div -> num % div = 0) divisors 

let minNumDividedBy (divisors: int[]) = 
    let rec minNumDividedByAll stopAt acc = 
     if acc >= stopAt then 0 
     else if isDivisableByAll acc divisors then acc 
     else minNumDividedByAll stopAt (acc + 1) 
    minNumDividedByAll 400000000 1 

minNumDividedBy [|1..20|] 

私はより少ないコードを好み、次のように書いていたので、よりエレガントにすることができると思いました。

let answer = { 1..400000000 } 
      |> Seq.tryFind (fun el -> isDivisableByAll el [|1..20|]) 

10分かかりました。シーケンスが怠けているので、大きな違いは説明できませんでした。調査するために、私は命令的なループを書いた。

let mutable i = 1 
while i < 232792561 do 
    if isDivisableByAll i [|1..20|] then 
     printfn "%d" i 
    i <- i + 1 

8分かかりました。したがって、シーケンスの障害でもありません。だから、なぜ初期の関数はとても速いのですか？それは、尾の再帰のためにスタックを構築することを避けることはできません、それはできますか？なぜなら、スローな例の中にビルドされていると、私はかなりのスタックを期待していないからです。

私には分かりませんが、誰かが私に教えてくれますか？

ありがとうございます。

Answer 1

Fyodor Soikinがコメントしたように、seqソリューションの各繰り返しで新しい配列[|1..20|]を作成することが主な原因です。配列を一度定義して渡すと、再帰的な解法では27秒に比べて10秒で実行できます。残っている不一致は、ループの末尾に最適化された再帰と比較して、レイジーシーケンスの場合に必要とされる追加の機械にまで及ぶ必要があります。

インライン関数をisDivisableByAllにすると、再帰的ソリューション（6秒まで）に大きな違いが生じます。これは、seqソリューションには影響していないようです。

Answer 2

私が正しく理解していれば、あなたは20まで1からのすべての数字で割り切れるされているどのように多くの数字1と4億の間（両端を含む）を見つけるためにしようとしている私はそれを自分自身の粗製のバージョン作られた：

let factors = Array.rev [| 2 .. 20 |] 

let divisible f n = 
    Array.forall (fun x -> n % x = 0) f 

let solution() = 
    {1 .. 400000000} 
    |> Seq.filter (divisible factors) 
    |> Seq.length 

を

このソリューションは、テストしたところで実行するのに90秒以上かかる。しかし、私はそれがオイラーの問題番号5の変形であることを認識するようになりました.2520は1から10までのすべての数で割り切れる最初の数であることがわかります。この事実を利用して、2520の倍数のシーケンスを作成できます。試験のみ倍数が1から10までのすべての数で割り切れることが保証されているように11から19までの数字、および20ならびに：

let factors = Array.rev [| 11 .. 19 |] 

let divisible f n = 
    Array.forall (fun x -> n % x = 0) f 

let solution() = 
    Seq.initInfinite (fun i -> (i + 1) * 2520) 
    |> Seq.takeWhile (fun i -> i <= 400000000) 
    |> Seq.filter (divisible factors) 
    |> Seq.length 

この溶液を0.191秒を要します。

オイラー問題番号5についてわからない場合は、与えられた開始値の倍数である要素を持つシーケンスをアルゴリズムで計算することさえできます。このアルゴリズムには、2からn-1までのすべての数で割り切れる数列が与えられ、2からnまでのすべての数で割り切れる最初の数が計算されます。

let narrowDown m n s = 
    (s, {m .. n}) 
    ||> Seq.fold (fun a i -> 
      let j = Seq.find (fun x -> x % i = 0) a 
      Seq.initInfinite (fun i -> (i + 1) * j)) 

let solution() = 
    Seq.initInfinite (fun i -> i + 1) 
    |> narrowDown 2 20 
    |> Seq.takeWhile (fun i -> i <= 400000000) 
    |> Seq.length 

このソリューションは、0.018秒で実行されます：私たちは私たちが望むすべての要因で割り切れる最初の数の倍数の配列を有してまで、これが通じ繰り返されます。