Come migliorare le prestazioni con idiomi F #

Question

Sto utilizzando this course on Machine-Learning per imparare F # allo stesso tempo. Ho svolto i seguenti compiti exercise che è il primo esercizio della seconda settimana:

Eseguire una simulazione al computer per lanciare 1.000 monete virtuali. Flip ogni moneta in modo indipendente 10 volte. Focus su 3 monete come segue: c1 è la prima moneta capovolto, crand è una moneta scelta a caso dal del 1000, e cmin è la moneta che aveva la frequenza minima di teste (scegliere il meno un in caso di parità).

Let ν1, νrand e νmin tramite la frazione di teste ottenuti per le rispettive 3 monete dei 10 lanci. Esegui l'esperimento 100.000 volte nell'ordine per ottenere una distribuzione completa di ν1, νrand e νmin (nota che c rand e c min cambieranno da esecuzione a esecuzione).

Qual è il valore medio di νmin?

ho prodotto il seguente codice, che funziona bene e dà la risposta corretta:

let private rnd = System.Random() 
let FlipCoin() = rnd.NextDouble() > 0.5 
let FlipCoinNTimes N = List.init N (fun _ -> FlipCoin()) 
let FlipMCoinsNTimes M N = List.init M (fun _ -> FlipCoinNTimes N) 

let ObtainFrequencyOfHeads tosses = 
    let heads = tosses |> List.filter (fun toss -> toss = true) 
    float (List.length (heads))/float (List.length (tosses)) 

let GetFirstRandMinHeadsFraction allCoinsLaunchs = 
    let first = ObtainFrequencyOfHeads(List.head (allCoinsLaunchs)) 
    let randomCoin = List.item (rnd.Next(List.length (allCoinsLaunchs))) allCoinsLaunchs 
    let random = ObtainFrequencyOfHeads(randomCoin) 

    let min = 
     allCoinsLaunchs 
     |> List.map (fun coin -> ObtainFrequencyOfHeads coin) 
     |> List.min 
    (first, random, min) 

module Exercice1 = 
    let GetResult() = 
     Seq.init 100000 (fun _ -> FlipMCoinsNTimes 1000 10) 
     |> Seq.map (fun oneExperiment -> GetFirstRandMinHeadsFraction oneExperiment) 
     |> Seq.map (fun (first, random, min) -> min) 
     |> Seq.average 

Tuttavia, ci vuole circa 4 minuti per correre nella mia macchina. So che sta facendo molto lavoro, ma mi chiedo se ci siano alcune modifiche che potrebbero essere apportate per ottimizzarlo.

Mentre sto cercando di imparare F #, sto chiedendo delle ottimizzazioni che usano gli idi di F #, non di cambiare il codice in uno stile C.

Sentitevi liberi di suggerire alcun tipo di miglioramento, in stile, le buone pratiche, ecc

[UPDATE]

ho scritto del codice per confrontare le soluzioni proposte, è accessibile here.

Questi sono i risultati:

Base - Risultato: 0.037510, il tempo trascorso: 00: 00: 55,1,274883 millions, miglioramento: 0.99 x

Matthew McVeigh - risultato: 0,037,497 mila, il tempo trascorso: 00 : 00: 15,1,682052 millions, miglioramento: 3,61 x

Fyodor Soikin - risultato: 0,037,524 mila, il tempo trascorso: 00: 01: 29,7,168787 millions, miglioramento: 0.61 x

GuyCoder - risultato: 0,037,645 mila, Tempo trascorso: 00: 00: 02,0883482, miglioramento: 26.25 x

risultato GuyCoder MathNet-: 0,037,666 mila, il tempo trascorso: 00: 00: 24,7,596117 millions, miglioramento: 2.21 x

TheQuickBrownFox - risultato: 0,037,494 mila, il tempo trascorso: 00: 00: 34,2,831239 millions, miglioramento: 1.60 x

Il vincitore, relativa al miglioramento nel tempo è il GuyCoder, quindi accetterò la sua risposta. Tuttavia, trovo che il suo codice sia più difficile da capire.

Answer 1

in esecuzione il codice sul mio computer e la tempistica ottengo:

seconds: 68.481918 
result: 0.47570994 

esecuzione il mio codice sul mio computer e la tempistica ottengo:

seconds: 14.003861 
vOne: 0.498963 
vRnd: 0.499793 
vMin: 0.037675 

con VMIN di essere più vicino alla risposta corretta di b essendo 0.01

Questo è quasi 5x più veloce.

Non mi sono occupato di ogni metodo e struttura dei dati per capire perché e cosa ha funzionato, ho solo usato decenni di esperienza per guidarmi. Chiaramente non memorizzando i valori intermedi, ma solo i risultati sono un grande miglioramento. Nello specifico, coinTest restituisce semplicemente il numero di teste che è uno int e non un elenco di risultati. Inoltre, invece di ottenere un numero casuale per ogni coin flip ma ottenere un numero casuale per ogni moneta e quindi usare ciascuna parte di quel numero casuale come un coin flip, è vantaggioso. Ciò consente di salvare le chiamate number of flips - 1 a una funzione. Inoltre ho evitato di usare i valori float fino alla fine; Non considero che risparmiare tempo sulla CPU, ma semplifica il processo di pensiero del solo pensiero in int che mi ha permesso di concentrarmi su altre efficienze. So che può sembrare strano ma meno devo pensare a meglio le risposte che ottengo. Ho anche eseguito solo coinTest quando era necessario, ad es. solo la prima moneta, solo la moneta casuale, e ha cercato tutte le code come condizione di uscita.

namespace Workspace 

module main = 

    [<EntryPoint>] 
    let main argv = 

     let rnd = System.Random() 
     let randomPick (limit : int) : int = rnd.Next(limit) // [0 .. limit) it's a Python habit 

     let numberOfCoins = 1000 
     let numberOfFlips = 10 
     let numberOfExperiements = 100000 

     let coinTest (numberOfFlips : int) : int = 
      let rec countHeads (flips : int) bitIndex (headCount : int) : int = 
       if bitIndex < 0 then headCount 
       else countHeads (flips >>> 1) (bitIndex-1) (headCount + (flips &&& 0x01)) 
      countHeads (randomPick ((pown 2 numberOfFlips) - 1)) numberOfFlips 0 

     let runExperiement (numberOfCoins : int) (numberOfFlips : int) : (int * int * int) = 
      let (randomCoin : int) = randomPick numberOfCoins 
      let rec testCoin coinIndex (cFirst, cRnd, cMin, cFirstDone, cRanDone, cMinDone) : (int * int * int) = 
       if (coinIndex < numberOfCoins) then 
        if (not cFirstDone || not cRanDone || not cMinDone) then 
         if (cFirstDone && cMinDone && (coinIndex <> randomCoin)) then 
          testCoin (coinIndex+1) (cFirst, cRnd, cMin, cFirstDone, cRanDone, cMinDone) 
         else 
          let headsTotal = coinTest numberOfFlips 
          let (cFirst, cRnd, cMin, cFirstDone, cRanDone, cMinDone) = 
           let cFirst = if coinIndex = 0 then headsTotal else cFirst 
           let cRnd = if coinIndex = randomCoin then headsTotal else cRnd 
           let cMin = if headsTotal < cMin then headsTotal else cMin 
           let cRanDone = if (coinIndex >= randomCoin) then true else cRanDone 
           let cMinDone = if (headsTotal = 0) then true else cMinDone 
           (cFirst, cRnd, cMin, true, cRanDone, cMinDone) 
          testCoin (coinIndex+1) (cFirst, cRnd, cMin, cFirstDone, cRanDone, cMinDone) 
        else 
         (cFirst, cRnd, cMin) 
       else 
        (cFirst, cRnd, cMin) 
      testCoin 0 (-1,-1,10, false, false, false) 

     let runExperiements (numberOfExperiements : int) (numberOfCoins : int) (numberOfFlips : int) = 
      let rec accumateExperiements index aOne aRnd aMin : (int * int * int) = 
       let (cOne,cRnd,cMin) = runExperiement numberOfCoins numberOfFlips 
       if index > numberOfExperiements then (aOne, aRnd, aMin) 
       else accumateExperiements (index + 1) (aOne + cOne) (aRnd + cRnd) (aMin + cMin) 
      let (aOne, aRnd, aMin) = accumateExperiements 0 0 0 0 
      let (vOne : double) = (double)(aOne)/(double)numberOfExperiements/(double)numberOfFlips 
      let (vRnd : double) = (double)(aRnd)/(double)numberOfExperiements/(double)numberOfFlips 
      let (vMin : double) = (double)(aMin)/(double)numberOfExperiements/(double)numberOfFlips 
      (vOne, vRnd, vMin) 

     let timeIt() = 
      let stopWatch = System.Diagnostics.Stopwatch.StartNew() 
      let (vOne, vRnd, vMin) = runExperiements numberOfExperiements numberOfCoins numberOfFlips 
      stopWatch.Stop() 
      printfn "seconds: %f" (stopWatch.Elapsed.TotalMilliseconds/1000.0) 
      printfn "vOne: %A" vOne 
      printfn "vRnd: %A" vRnd 
      printfn "vMin: %A" vMin 

     timeIt() 

     printf "Press any key to exit: " 
     System.Console.ReadKey() |> ignore 
     printfn "" 

     0 // return an integer exit code 

=========================================== ===============

Questa è solo una risposta intermedia perché ho chiesto se l'OP considerava l'uso di MathNet Numerics F # e l'OP volevano vedere com'era. Dopo aver eseguito la sua versione e questa versione di primo taglio sulla mia macchina, la versione OP è più veloce. OP: 75 secondi, il mio: 84 secondi

namespace Workspace 

open MathNet.Numerics.LinearAlgebra 

module main = 

    [<EntryPoint>] 
    let main argv = 

     let rnd = System.Random() 
     let flipCoin() = 
      let head = rnd.NextDouble() > 0.5 
      if head then 1.0 else 0.0 

     let numberOfCoins = 1000 
     let numberOfFlips = 10 
     let numberOfExperiements = 100000 
     let numberOfValues = 3 

     let randomPick (limit : int) : int = rnd.Next(limit) // [0 .. limit) it's a Python habit 
     let headCount (m : Matrix<float>) (coinIndex : int) : int = 
      System.Convert.ToInt32((m.Row coinIndex).Sum()) 

     let minHeads (m : Matrix<float>) (numberOfCoins : int) (numberOfFlips : int) : int = 
      let rec findMinHeads currentCoinIndex minHeadsCount minHeadsIndex = 
       match currentCoinIndex,minHeadsCount with 
       | -1,_ -> minHeadsCount 
       | _,0 -> minHeadsCount // Can't get less than zero so stop searching. 
       | _ -> 
        let currentMinHeadCount = (headCount m currentCoinIndex) 
        let nextIndex = currentCoinIndex - 1 
        if currentMinHeadCount < minHeadsCount 
        then findMinHeads nextIndex currentMinHeadCount currentCoinIndex 
        else findMinHeads nextIndex minHeadsCount minHeadsIndex 
      findMinHeads (numberOfCoins - 1) numberOfFlips -1 

     // Return the values for cOne, cRnd, and cMin as int values. 
     // Will do division on final sum of experiments instead of after each experiment. 
     let runExperiement (numberOfCoins : int) (numberOfFlips : int) : (int * int * int) =   
      let (flips : Matrix<float>) = DenseMatrix.init numberOfCoins numberOfFlips (fun i j -> flipCoin()) 
      let cOne = headCount flips 0 
      let cRnd = headCount flips (randomPick numberOfCoins) 
      let cMin = minHeads flips numberOfCoins numberOfFlips 
      (cOne,cRnd,cMin) 

     let runExperiements (numberOfExperiements : int) (numberOfCoins : int) (numberOfFlips : int) : (int [] * int [] * int []) = 
      let (cOneArray : int[]) = Array.create numberOfExperiements 0 
      let (cRndArray : int[]) = Array.create numberOfExperiements 0 
      let (cMinArray : int[]) = Array.create numberOfExperiements 0 
      for i = 0 to (numberOfExperiements - 1) do 
       let (cOne,cRnd,cMin) = runExperiement numberOfCoins numberOfFlips 
       cOneArray.[i] <- cOne 
       cRndArray.[i] <- cRnd 
       cMinArray.[i] <- cMin 
      (cOneArray, cRndArray, cMinArray) 

     let (cOneArray, cRndArray, cMinArray) = runExperiements numberOfExperiements numberOfCoins numberOfFlips 
     let (vOne : double) = (double)(Array.sum cOneArray)/(double)numberOfExperiements/(double)numberOfFlips 
     let (vRnd : double) = (double)(Array.sum cRndArray)/(double)numberOfExperiements/(double)numberOfFlips 
     let (vMin : double) = (double)(Array.sum cMinArray)/(double)numberOfExperiements/(double)numberOfFlips 

     printfn "vOne: %A" vOne 
     printfn "vRnd: %A" vRnd 
     printfn "vMin: %A" vMin 

a metà della codifica mi sono reso conto che potevo fare tutti i calcoli utilizzando solo int, è stato solo gli ultimi calcoli che hanno generato le percentuali che doveva essere un float o double e anche allora è solo perché l'elenco delle risposte è una percentuale; in teoria i numeri possono essere confrontati come int per ottenere la stessa comprensione. Se uso solo lo int, allora dovrei creare un tipo di Matrix int e questo è più lavoro di quanto io voglia fare. Quando avrò tempo, cambierò MathNet Matrix con un F # Array2D o qualcosa di simile e controllarlo. Notare se si codifica questo con MathNet quindi il maintainer di MathNet potrebbe rispondere (Christoph Rüegg)

Ho apportato una modifica a questo metodo ed è più veloce di 5 secondi.

// faster 
let minHeads (m : Matrix<float>) (numberOfCoins : int) (numberOfFlips : int) : int = 
    let (mins : float[]) = m.FoldByRow((fun (x : float) y -> x + y), 0.0) 
    let (minHead : float) = Array.min mins 
    System.Convert.ToInt32(minHead) 

Answer 2

Allocare una grande quantità di liste in anticipo è un lavoro pesante, l'algoritmo può essere elaborato in linea ad esempio tramite sequenze o ricorsione. Ho trasformato tutto il lavoro in funzioni ricorsive di coda per un po 'la velocità prima (sarà trasformato in loop dal compilatore)

non garantito per essere corretta al 100%, ma spero che ti dà una sostanza di dove stavo andando con esso :

let private rnd = System.Random() 
let flipCoin() = rnd.NextDouble() > 0.5 

let frequencyOfHeads flipsPerCoin = 
    let rec countHeads numHeads i = 
     if i < flipsPerCoin then 
      let isHead = flipCoin() 
      countHeads (if isHead then numHeads + 1 else numHeads) (i + 1) 
     else 
      float numHeads 

    countHeads 0 0/float flipsPerCoin 

let getFirstRandMinHeadsFraction numCoins flipsPerCoin = 
    let randomCoinI = rnd.Next numCoins 

    let rec run first random min i = 
     if i < numCoins then 
      let frequency = frequencyOfHeads flipsPerCoin 
      let first = if i = 0 then frequency else first 
      let random = if i = randomCoinI then frequency else random 
      let min = if min > frequency then frequency else min 

      run first random min (i + 1) 
     else 
      (first, random, min) 

    run 0.0 0.0 System.Double.MaxValue 0 

module Exercice1 = 
    let getResult() = 
     let iterations, numCoins, numFlips = 100000, 1000, 10 

     let getMinFromExperiment() = 
      let (_, _, min) = getFirstRandMinHeadsFraction numCoins numFlips 
      min 

     let rec sumMinFromExperiments i sumOfMin = 
      if i < iterations then 
       sumMinFromExperiments (i + 1) (sumOfMin + getMinFromExperiment()) 
      else 
       sumOfMin 

     let sum = sumMinFromExperiments 0 0.0 
     sum/float iterations 

Answer 3

Ho cercato di trovare le più piccole modifiche possibili al codice per renderlo più veloce.

Il più grande miglioramento delle prestazioni che ho riscontrato è stato modificare la funzione ObtainFrequencyOfHeads in modo che contenga i valori true nella raccolta anziché creare una raccolta filtrata intermedia e quindi contarli. Ho fatto questo utilizzando fold:

let ObtainFrequencyOfHeads tosses = 
    let heads = tosses |> List.fold (fun state t -> if t then state + 1 else state) 0 
    float heads/float (List.length (tosses)) 

Un altro miglioramento è venuto di modificare tutte le liste in array. Questo è stato semplice come sostituire ogni istanza di List. con Array. (inclusa la nuova funzione sopra).

Alcuni potrebbero dire che questo è meno funzionale, perché utilizza una collezione mutevole invece di una immutabile. Tuttavia, non stiamo mutando alcun array, semplicemente usando il fatto che sono poco costosi da creare, controllarne la lunghezza e cercare per indice. Abbiamo rimosso una restrizione sulla mutazione, ma non stiamo ancora utilizzando la mutazione. È certamente F # idiomatico utilizzare array per prestazioni, se necessario.

Con entrambi questi cambiamenti ho ottenuto quasi un miglioramento delle prestazioni 2x in FSI.