For a simple problem, see Project Euler #1, I thought it would an interesting exercise to code alternative implementations and time them. You see, when I originally solved the problem way back in the mists of time (well, perhaps not that long ago as it was done using F# 1.9.9 as far as I recall) I was using PE as a tool to teach myself F#. Nowadays I'm comfortable with F# so I thought I would return to PE and explore a little more.
So, follows is some F# code which solves problem #1. Spoiler alert! If you haven't already solved it and intend to do so, stop reading now!
let first = fun (a,b) -> a
let second = fun (a,b) -> b
let upperLimit = 1000 // ie we want to act upon the integers which are less than 1000
let maxLoops = 25000 // an arbitrary large integer - the number of times to repeat the core calculation in a single (timed) execution
let howMany = 15 // ie the number of times we want to perform the calculation in order to find the average calculation time
let st = new System.Diagnostics.Stopwatch()
let Impl1a = fun () ->
let whichImpl = "Iteration"
st.Restart()
for loop = 1 to maxLoops do
let mutable sum = 0
for i = 1 to upperLimit-1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl1b = fun () ->
let whichImpl = "Iteration with mutable creation outside loop"
st.Restart()
let mutable sum = 0
for loop = 1 to maxLoops do
sum <- 0
for i = 1 to upperLimit-1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl1c = fun () ->
let whichImpl = "Reverse iteration"
st.Restart()
for loop = 1 to maxLoops do
let mutable sum = 0
for i = upperLimit-1 downto 1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl1d = fun () ->
let whichImpl = "Reverse iteration with mutable creation outside loop"
st.Restart()
let mutable sum = 0
for loop = 1 to maxLoops do
sum <- 0
for i = upperLimit-1 downto 1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2a = fun () ->
let whichImpl = "Iteration using List higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = [1..upperLimit-1] |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2b = fun () ->
let whichImpl = "Iteration using List higher-order fns with pre-compiled integer range"
st.Restart()
let input = [1..upperLimit-1]
for loop = 1 to maxLoops do
let sum = input |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2c = fun () ->
let whichImpl = "Iteration using Seq higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = seq {1 .. upperLimit-1} |> Seq.filter (fun i -> i%3=0 || i%5=0) |> Seq.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2d = fun () ->
let whichImpl = "Reverse Iteration using List higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = [upperLimit-1 .. -1 .. 1] |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2e = fun () ->
let whichImpl = "Reverse Iteration using List higher-order fns with pre-compiled integer range"
st.Restart()
let input = [upperLimit-1 .. -1 .. 1]
for loop = 1 to maxLoops do
let sum = input |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2f = fun () ->
let whichImpl = "Reverse Iteration using Seq higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = seq {upperLimit-1 .. -1 .. 1} |> Seq.filter (fun i -> i%3=0 || i%5=0) |> Seq.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl3a = fun () ->
let whichImpl = "Recursion with Accumulator"
let rec Impl3p counter acc =
if counter=upperLimit then
acc
else if counter%3=0 || counter%5=0 then
Impl3p (counter+1) (acc+counter)
else
Impl3p (counter+1) acc
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl3p 1 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl3b = fun () ->
let whichImpl = "Recursion"
let rec Impl3p counter =
if counter=upperLimit then
0
else if counter%3=0 || counter%5=0 then
counter + Impl3p (counter+1)
else
Impl3p (counter+1)
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl3p 1
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl4a = fun () ->
let whichImpl = "Iteration incrementing a pair of counters"
st.Restart()
for loop = 1 to maxLoops do
let mutable sum = 0
let mutable loopDiv3,loopDiv5 = 0,0
while loopDiv3<upperLimit do // because loopDiv3 increases slower than loopDiv5
loopDiv3 <- loopDiv3 + 3
loopDiv5 <- loopDiv5 + 5
// if we haven't already added it in loopDiv5 ...
sum <- sum + (if loopDiv3 < upperLimit then (if loopDiv3 % 5 <> 0 then loopDiv3 else 0) else 0)
sum <- sum + (if loopDiv5 < upperLimit then loopDiv5 else 0)
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl4b = fun () ->
let whichImpl = "Recursion using a pair of counters"
let rec Impl4p counterDiv3 counterDiv5 =
if counterDiv3>=upperLimit then
0
else
(if counterDiv3 % 5 <> 0 then counterDiv3 else 0) + (if counterDiv5 < upperLimit then counterDiv5 else 0) + Impl4p (counterDiv3+3) (counterDiv5+5)
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl4p 0 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl4c = fun () ->
let whichImpl = "Recursion with Accumulator using a pair of counters"
let rec Impl4p counterDiv3 counterDiv5 acc =
if counterDiv3>=upperLimit then
acc
else
Impl4p (counterDiv3+3) (counterDiv5+5) ((if counterDiv3 % 5 <> 0 then counterDiv3 else 0) + (if counterDiv5 < upperLimit then counterDiv5 else 0) + acc)
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl4p 0 0 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let run (whichImpl : unit -> int64 * string) =
let res = [ for count = 1 to howMany do yield whichImpl() ]
let name = res |> List.head |> second
let elapsed = res |> List.map first
elapsed |> List.iter (fun elem -> printfn "%s : %i iterations took %i milliseconds" name maxLoops elem)
let avg = float (elapsed |> List.fold (fun state i -> state+i) 0L) / float (List.length elapsed)
name, avg
let implementations = [ Impl1a; Impl1b; Impl1c; Impl1d; Impl2a; Impl2b; Impl2c; Impl2d; Impl2e; Impl2f; Impl3a; Impl3b; Impl4a; Impl4b; Impl4c ]
implementations |> List.map (fun impl -> run impl)
Well, well! How interesting! Using F# interactive, these are the results obtained from my test run:
[("Iteration", 252.8);
("Iteration with mutable creation outside loop", 255.0666667);
("Reverse iteration", 225.0);
("Reverse iteration with mutable creation outside loop", 236.1333333);
("Iteration using List higher-order fns", 3509.933333);
("Iteration using List higher-order fns with pre-compiled integer range", 386.6);
("Iteration using Seq higher-order fns", 4848.933333);
("Reverse Iteration using List higher-order fns", 3679.466667);
("Reverse Iteration using List higher-order fns with pre-compiled integer range", 396.7333333);
("Reverse Iteration using Seq higher-order fns", 4883.266667);
("Recursion", 242.4);
("Recursion with Accumulator", 231.9333333);
("Iteration incrementing a pair of counters", 48.6);
("Recursion using a pair of counters", 90.4);
("Recursion with Accumulator using a pair of counters", 53.26666667)]
No comments:
Post a Comment