2016-06-20 13 views
7

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.

+4

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. –

+1

pigro = non veloce :-) – s952163

+1

Naturalmente, c'è un modo molto più semplice per farlo con un cambio algoritmico. –

risposta

4

Come ha commentato Fyodor Soikin, creare un nuovo array [|1..20|] per ogni iterazione nella soluzione seq è il colpevole principale. Se definisco l'array una volta e lo passo, posso eseguirlo in 10 secondi, rispetto ai 27 secondi della soluzione ricorsiva. La disparità rimanente deve essere dovuta al macchinario aggiuntivo necessario in giro per una sequenza lenta, rispetto alla ricorsione che è ottimizzata in un ciclo for.

Fare la isDivisableByAll una funzione in linea fa una differenza significativa per la soluzione ricorsiva (fino a 6 secondi). Non sembra influire sulla soluzione seq.

+0

Oh mio dio pensavo di aver provato a spostare la comprensione dell'array, ma ovviamente non l'avevo fatto. Grazie. – chr1st0scli

+1

Si potrebbe immaginare che F # creerebbe un ciclo efficiente per l'espressione 'Seq' ma al momento non lo fa. Invece viene creato un 'Seq' e come @TheQuickBrownFox dice che il sovraccarico dell'enumerazione su di esso probabilmente spiega la differenza (2 chiamate virtuali e implementazioni F #' Seq' non sembrano efficaci come LINQ). Detto ciò cambiando il modo in cui calcoli la risposta puoi usare 'Seq' e produrre la risposta in meno di 1 ms. – FuleSnabel

+3

Si potrebbe provare a utilizzare Nessos 'Stream 'e vedere come questo si confronta. – FuleSnabel

5

Se ho capito bene, si sta cercando di trovare quanti numeri compresi tra 1 e 400 milioni (compreso) sono divisibili per tutti i numeri da 1 a 20. Ho fatto la mia versione grezza di esso:

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 

Questa soluzione richiede più di 90 secondi per essere eseguita dove l'ho provata. Ma mi sono reso conto che è una variazione del problema numero 5 di Eulero, in cui apprendiamo che 2520 è il primo numero divisibile da tutti i numeri da 1 a 10. Usando questo fatto, possiamo creare una sequenza di multipli di 2520, e testare solo i numeri dall'11 al 19, i multipli sono garantiti per essere divisibile per tutti i numeri da 1 a 10, e 20 nonché:

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 

Questa soluzione richiede 0,191 secondi.

Se non si conosce il problema numero 5 di Eulero, è anche possibile calcolare algoritmicamente sequenze con elementi multipli di un dato valore iniziale. Diamo all'algoritmo una sequenza di numeri divisibili per tutti i numeri da 2 a n - 1, e calcola il primo numero divisibile per tutti i numeri da 2 a n. Questo è iterato attraverso finché non avremo una sequenza di multipli del primo numero divisibile per tutti i fattori che vogliamo:

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 

Questa soluzione viene eseguito in 0.018 secondi.

+0

Grazie. Per evitare di filtrarlo e limitarlo, puoi scriverlo come: let solution() = Seq.initInfinite (fun -> (i + 1) * 2520) |> Seq.tryFind (fattori divisibili) – chr1st0scli

+0

Seq.tryFind fa non calcoliamo esattamente la stessa cosa che vogliamo qui: fornisce il primo elemento che soddisfa il predicato, o None se non esiste. Ciò di cui abbiamo bisogno qui, tuttavia, è il numero di elementi nella sequenza (che capita di essere 1). – dumetrulo

+0

Questa idea è generalizzabile quindi non è richiesta alcuna conoscenza preventiva – FuleSnabel

Problemi correlati