F # Leistungsunterschied zwischen Tail-Rekursion und Seq-Bibliothek

Question

Ich habe diesen Code in F #, der die kleinste positive Zahl findet, die durch alle Zahlen von 1 bis 20 teilbar ist. Es dauert 10 Sekunden.

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|] 

Also dachte ich, ich könnte es eleganter machen, weil ich weniger Code bevorzuge und schrieb folgendes.

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

Es dauerte 10 Minuten! Ich konnte den großen Unterschied nicht erklären, da Sequenzen faul sind. Um zu untersuchen, schrieb ich eine Imperativschleife.

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

Es dauerte 8 Minuten. Deshalb ist es auch nicht die Sequenz, richtig? Also, warum ist die anfängliche Funktion so schnell? Es kann nicht vermieden werden, den Stack aufgrund der Schwanzrekursion aufzubauen, oder? Weil ich nicht erwarten würde, dass ein beträchtlicher Stapel, wenn überhaupt, in den langsamen Beispielen entweder gebaut wird.

Es macht nicht viel Sinn für mich, kann mir jemand sagen?

Vielen Dank.

Answer 1

Wie Fyodor Soikin kommentierte, ist die Hauptursache ein neues Array [|1..20|] für jede Iteration in der seq Lösung. Wenn ich das Array einmal definiere und es übergebe, kann ich es in 10 Sekunden ausführen, verglichen mit 27 Sekunden für die rekursive Lösung. Die verbleibende Disparität muss auf die zusätzliche Maschinerie zurückzuführen sein, die für eine Lazy-Sequenz benötigt wird, verglichen mit der Rekursion, die Tail-Call in eine For-Schleife optimiert.

Die isDivisableByAll Inline-Funktion macht einen signifikanten Unterschied für die rekursive Lösung (bis zu 6 Sekunden). Es scheint die seq Lösung nicht zu beeinflussen.

Answer 2

Wenn ich richtig verstehe, Sie versuchen, wie viele Zahlen zwischen 1 und 400 Mio. (einschließlich) sind von allen Zahlen von 1 bis 20. Ich meine eigene Roh-Version davon gemacht teilbar zu finden:

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 

Diese Lösung dauert über 90 Sekunden, wo ich sie getestet habe. Aber ich erkannte, dass es eine Variation des Euler-Problems Nummer 5 ist, wo wir erfahren, dass 2520 die erste Zahl ist, die durch alle Zahlen von 1 bis 10 teilbar ist. Mit dieser Tatsache können wir eine Folge von Vielfachen von 2520 und Test nur die Zahlen 11 bis 19, da die mehrfachen garantiert werden von allen Zahlen von 1 bis 10 und 20 als auch teilbar sein:

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 

Diese Lösung 0,191 Sekunden dauert.

Wenn Sie das Euler-Problem Nummer 5 nicht kennen, können Sie sogar Sequenzen mit Elementen berechnen, die ein Vielfaches eines gegebenen Anfangswertes sind. Wir geben dem Algorithmus eine Folge von Zahlen, die durch alle Zahlen von 2 bis n - 1 teilbar sind, und er berechnet die erste Zahl, die durch alle Zahlen von 2 bis n teilbar ist. Dies wird wiederholt, bis, bis wir eine Folge von Vielfachen der ersten Zahl teilbar durch alle Faktoren haben wir wollen:

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 

Diese Lösung in 0,018 Sekunden läuft.