我同时在机器学习中使用本课程来学习F#。我已经完成了以下家庭作业练习,这是第二周的第一次练习:
运行计算机模拟以翻转1,000个虚拟公平硬币。独立翻转每个硬币10次。重点关注以下3个硬币:c1是第一个翻转的硬币,crand是从1,000个硬币中随机选择的硬币,而cmin是具有最小正面频率的硬币(如果打成平局,则选择较早的一个)。
让ν1,νrand,和νmin是为3枚各自硬币获得了10次投掷的头部分。运行该实验100,000次,以获得ν1,νrand和νmin的完整分布(请注意,crand和cmin会随运行而变化)。
ν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样式。
随意提出任何改进的方式,例如风格,良好做法等。
[更新]
结果如下:
基本-结果:0.037510,经过的时间:00:00:55.1274883,改进:0.99 x
Matthew Mcveigh-结果:0.037497,已用时间:00:00:15.1682052,改进:3.61 x
Fyodor Soikin-结果:0.037524,经过时间:00:01:29.7168787,改进:0.61 x
GuyCoder-结果:0.037645,经过的时间:00:00:02.0883482,改进时间:26.25 x
GuyCoder MathNet-结果:0.037666,经过的时间:00:00:24.7596117,改进:2.21 x
TheQuickBrownFox-结果:0.037494,经过的时间:00:00:34.2831239,改进:1.60 x
关于时间改进的优胜者是GuyCoder,所以我将接受他的回答。但是,我发现他的代码更难以理解。
在计算机上运行您的代码并计时:
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
值直到最后。我不认为可以节省CPU时间,但是确实简化了仅在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
================================================== ======================
这只是一个中间答案,因为我询问OP是否考虑使用MathNet Numerics惯用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
在编码过程的一半,我意识到我可以使用just完成所有计算int
,只有最后一次计算才能生成需要为afloat
或a的百分比,double
即使那样,那也是因为答案列表是一个百分比。从理论上讲,可以对数字进行比较int
以获得相同的理解。如果仅使用,int
则必须创建一个int
Matrix类型,这比我想做的工作还要多。当我有时间的时候,我将把MathNet矩阵切换到F#Array2D或类似的东西,然后检查一下。请注意,如果用标记,MathNet
则MathNet
可能会回答(克里斯托夫·吕格(ChristophRü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)
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句