Ho questo codice in F # che trova il numero positivo più piccolo che è equamente divisibile per tutti i numeri da 1 a 20. Ci vogliono 10 secondi per completare.F # differenza di prestazioni tra ricorsione coda e libreria Seq
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|]
Così, ho pensato che avrei potuto renderlo più elegante, perché preferisco meno codice e ha scritto quanto segue.
let answer = { 1..400000000 }
|> Seq.tryFind (fun el -> isDivisableByAll el [|1..20|])
Ci sono voluti 10 minuti! Non potrei spiegare l'enorme differenza, dal momento che le sequenze sono pigre. Nel tentativo di indagare, ho scritto un ciclo imperativo.
let mutable i = 1
while i < 232792561 do
if isDivisableByAll i [|1..20|] then
printfn "%d" i
i <- i + 1
Sono occorsi 8 minuti. Pertanto, non è nemmeno colpa della sequenza, giusto? Quindi, perché la funzione iniziale è così veloce? Non si può evitare di costruire la pila, a causa della ricorsione della coda, vero? Perché non mi aspetterei che uno stack considerevole, se presente, venga costruito anche negli esempi lenti.
Non ha molto senso per me, qualcuno può dirmelo?
Grazie.
Nel secondo esempio, si assegna un nuovo array ad ogni iterazione. Oltre a questo molte iterazioni deve aggiungere. Prova a creare prima l'array e poi a eseguire le iterazioni. –
pigro = non veloce :-) – s952163
Naturalmente, c'è un modo molto più semplice per farlo con un cambio algoritmico. –