Как улучшить производительность с помощью идиом F #

Question

Я использую this course on Machine-Learning, чтобы узнать F # одновременно. Я сделал следующее домашнее задание exercise, которое является первым упражнением второй недели:

Запустить компьютерное моделирование для переворачивания 1000 виртуальных ярмарочных монет. Flip каждая монета независимо 10 раз. Фокус на 3-х монет следующим образом: с1 это первая монета переворачивается, Форкан монета выбраны случайным образом из 1000, а Cmin это монета, которая имела минимальную частоту головок (выбрать более ранний в случае галстука).

Пусть ν1, νrand и νmin быть доля головок, полученных для соответствующих 3 монет из 10 бросков. Проведите эксперимент 100 000 раз, чтобы получить , чтобы получить полное распределение ν1, νrand и νmin (обратите внимание, что c rand и c min будут меняться от запуска до запуска).

Средняя оценка: νmin?

Я произвел следующий код, который отлично работает и дает правильный ответ:

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 

Однако, это занимает около 4 минут, чтобы работать в моей машине. Я знаю, что он много работает, но мне интересно, есть ли какие-то изменения, которые можно было бы оптимизировать.

Как я пытаюсь изучить F #, я прошу оптимизаций, которые используют идиомы F #, а не для изменения кода на C-стиль.

Вы можете предложить какие-либо улучшения, в стиле, передовой практики и т.д.

[UPDATE]

Я написал код, чтобы сравнить предлагаемые решения, является доступным here.

Таковы результаты:

Base - результат: 0.037510, истекшее время: 00: 00: 55.1274883, улучшение: 0,99 х

Мэтью Маквей - результат: 0,037497, истекшее время: 00 : 00: 15,1682052, улучшение: 3,61 х ​​

Федор Сойкин - результат: 0.037524, время, прошедшее: 00: 01: 29.7168787, улучшение: 0,61 х ​​

GuyCoder - результат: 0.037645, время, прошедшее: 00: 00: 02.0883482, улучшение: 26,25 х

GuyCoder MathNet- Результат: 0,037666, время, прошедшее: 00: 00: 24,7596117, улучшение: 2.21 х

TheQuickBrownFox - результат: 0,037494, истекшее время: 00: 00: 34.2831239, улучшение: 1,60 х

Победитель относительно улучшения времени является GuyCoder, так что я буду принимать его ответ. Однако я считаю, что его код сложнее понять.

Answer 1

Запуск кода на моем компьютере и времени я получаю:

seconds: 68.481918 
result: 0.47570994 

Запуск мой код на моем компьютере и времени я получаю:

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

с Vmin быть ближе всего к правильному ответу b являющееся 0.01

Это почти 5x быстрее.

Я не возился с каждым методом и структурой данных, чтобы выяснить, почему и что сработало, я просто использовал многолетний опыт, чтобы вести меня. Очевидно, что не сохранение промежуточных значений, а просто результаты являются большим улучшением. В частности, coinTest просто возвращает количество головок, которое является int, а не список результатов. Также вместо того, чтобы получать случайное число для каждого переворота монетки, но получая случайное число для каждой монеты, а затем использовать каждую часть этого случайного числа в качестве переворота монет выгодно. Это экономит number of flips - 1 вызовов функции. Также я избегал использовать значения float до самого конца; Я не считаю, что экономия времени на процессоре, но это упростило мыслительный процесс мышления только в int, что позволило мне сосредоточиться на других эффектах. Я знаю, что это может показаться странным, но чем меньше я должен думать о лучших ответах, которые получаю. Я также только побежал coinTest, когда это было необходимо, например. только первая монета, только случайная монета, и искал все хвосты в качестве условия выхода.

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 

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

Это лишь промежуточный ответ, потому что я спросил, если ОП рассматривается с использованием Mathnet Числовой идиоматическим F # и OP хотели посмотреть, как это выглядит. После запуска его версии и этой первой версии на моей машине версия OP работает быстрее. OP: 75 сек, шахта: 84 сек

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 

Хафвей через кодированию, я понял, что я мог сделать все расчеты с использованием только int, это было только последние расчеты, сгенерированные проценты, которые должны быть float или double, и даже тогда это только потому, что список ответов - это процент; в теории числа можно сравнить как int, чтобы получить то же понимание. Если я использую только int, тогда мне нужно будет создать тип матрицы int, и это больше, чем я хочу. Когда я получу время, я переключу MathNet Matrix на F # Array2D или что-то подобное и проверьте это. Обратите внимание, что если вы пометили его MathNet, то ответственный за MathNet может ответить (Christoph Rüegg)

Я внесла изменения в этот метод, и он быстрее на 5 секунд.

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

Выделение большого количества списков спереди - это тяжелая работа, алгоритм может обрабатываться онлайн, например. через последовательности или рекурсию. Я трансформировал всю работу в хвост рекурсивные функции для некоторого сырья скорости (будет преобразован в петлях компилятором)

не гарантирует 100% правильно, но, надеюсь, дает вам суть того, где я собирался с ним :

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

Я попытался найти минимально возможные изменения в вашем коде, чтобы ускорить его.

Наибольшее улучшение производительности, которое я обнаружил, было изменено функцией ObtainFrequencyOfHeads, так что она рассчитывает значения true в коллекции вместо создания промежуточной отфильтрованной коллекции, а затем подсчитывает ее. Я сделал это с помощью 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)) 

Другое усовершенствование пришло от изменения всех списков в массивы. Это было так же просто, как замена каждого экземпляра List. на Array. (включая новую функцию выше).

Некоторые могут сказать, что это менее функционально, потому что оно использует изменчивую коллекцию вместо неизменяемой. Однако мы не мутируем никаких массивов, просто используем тот факт, что они дешевы для создания, проверки длины и поиска по индексу. Мы удалили ограничение на мутацию, но мы по-прежнему не используем мутацию. Разумеется, идиоматический F # использовать массивы для производительности, если это необходимо.

С обоими этими изменениями я получил почти улучшение производительности в FSI.