After working for far too long on this, here is a review focusing mainly on performance issues, and possibly introducing some non functional stuff along the way. Lets take it problem by problem.
But let me start by stating that your code looks nice and clean, and without knowing any official style guides for F#, it is quite readable once you get a hang of the different F# idioms. One thing I think someone might mention though is to gather the open ... stuff at the beginning, and possibly to use multiline comments here and there.
Problem 1: Sum of multiples of 3 and 5
This being a rather simple variant, one could think there isn't much to optimize, but I found two issues to optimize your variant:
- Instead of using a in-place function as predicate for
Seq.filter use a predefined predicate. This cut down the time to 10 % of original time
- Instead of using a list, use a sequence to fill the pipe, this reduce the time by a third or so
But the really large saving is by changing algorithm to use the following formula for calculating the sum of factors of n below k: \$(n * m * (m + 1)/2\$ where \$m = (k - 1) / n\$. See https://codereview.stackexchange.com/a/280/78136 for more information on this rather fast imperative solution.
Using the following code for timing a function in F#:
(** My timing function ************************************************)
let time f =
let sw = System.Diagnostics.Stopwatch()
sw.Start()
let res = f()
sw.Stop()
(res, sw.Elapsed.TotalMilliseconds)
And the following extra code for first problem:
(******* Project Euler 1 : Sum of multiples of 3 and 5 ***************)
let sumFactorsOfNBelowK k n =
let m = ( k - 1 ) / n
n * m * ( m + 1 ) / 2
let mod3or5 x =
x % 3 = 0 || x % 5 = 0
let euler_1_org() = [ 1 .. 999 ] |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0) |> Seq.sum
let euler_1a_org() = [ 1 .. 999 ] |> Seq.filter mod3or5 |> Seq.sum
let euler_1b_org() = { 1 .. 999 } |> Seq.filter mod3or5 |> Seq.sum
let euler_1_v2() = sumFactorsOfNBelowK 1000 3 + sumFactorsOfNBelowK 1000 5 - sumFactorsOfNBelowK 1000 15
With a test block similar to:
let (euler1, time1) = time euler_1_org
let (euler1a, time1a) = time euler_1a_org
let (euler1b, time1b) = time euler_1b_org
let (euler1_v2, time1_v2) = time euler_1_v2
printfn "Solution to Project Euler 1"
printfn " Org: %i in %f ms" euler1 time1
printfn " A: %i in %f ms" euler1a time1a
printfn " B: %i in %f ms" euler1b time1b
printfn " v2: %i in %f ms" euler1_v2 time1_v2
I got the following output for problem 1:
Solution to Project Euler 1
Org: 233168 in 3.990900 ms
A: 233168 in 0.378200 ms
B: 233168 in 0.260800 ms
v2: 233168 in 0.037700 ms
Problem 2: Summing even Fibonaccy numbers
This one I tried various versions, but didn't find that much to optimize as it seems like your fibsRec is quite fast. Using the same trick as in previous problem, I almost halfed the time using a predefined isEven function.
Here is code:
(** Project Euler 2 : Sum of even Fibonacci under 4 million ***********)
let isEven n =
n % 2 = 0
let euler_2_org() = 1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter (fun x -> x % 2 = 0) |> Seq.sum
let euler_2_v2() = 1 :: 2 :: (fibsRec 1 2 4000000) |> Seq.filter isEven |> Seq.sum
And my output was:
Solution to Project Euler 2
Org: 4613732 in 0.592100 ms
v2a: 4613732 in 0.354700 ms
Problem 3: Max prime factor under n
As you most likely are aware of most of your solutions are brute force solutions, and therefore there does exist much faster solutions. I tried various alternatives, but soon found that doing stuff functional and with large numbers was as neat as I thought it should be. I guess the .Net shines through here somewhat.
An alternate implementation (mostly imperative) follows:
(** Project Euler 3 : Max prime factor under 600851475143L ************)
let findMaxPrimeFactor_v2 (number:int64) =
let mutable newNumber:int64 = number
let mutable largestFactor = 0L
let mutable counter = 2L
while counter * counter <= newNumber do
if newNumber % counter = 0L then
newNumber <- newNumber / counter
largestFactor <- counter
else
counter <- counter + 1L
if newNumber > largestFactor then
largestFactor <- newNumber
largestFactor
let euler_3_org() = findMaxPrimeFactor 600851475143L
let euler_3_v2() = findMaxPrimeFactor_v2 600851475143L
With timings:
Solution to Project Euler 3
Org: 6857 in 118.639500 ms
v2 : 6857 in 0.115400 ms
You could most likely shave a lot of your timings using sequences, change the step value, using predefine predicates and not to say using a prebuilt prime list (or memoization of some sort). I didn't get around doing that. I just implemented a way faster method... :-)
Problem 4: Largest palindrome product
Here I tried a little harder to actually follow your code and do some optimization on it. And the main optimization was the following two issues:
- Replace the
List.collect and List.map with a sequence of double for loop
- Change the loop to go downwards from 999 to 100 instead of upwards
After doing this which halved the running time, I discovered that F# doesn't have break or continue. Bummer. So I tried another version using while loops with flag variables, and this became the third variant on this solution. Extremely imperative, and kind of ugly for F# code to be (if I most say so myself!).
Here is the code:
(** Project Euler 4 : Largest palindrom of xxx*yyy ********************)
let findLargestPalindrome_v2 maximum minimum=
seq { for x in { maximum .. -1 .. minimum } do
for y in { x .. -1 .. minimum } do
yield x * y }
|> Seq.filter isPalindrome
|> Seq.max
let findLargestPalindrome_v3 maximum minimum=
let mutable maxPalindrome = 0
let outer_max = maximum
let outer_min = minimum
let inner_min = minimum
let mutable i = outer_max
let mutable outerLoop = true
while outerLoop do
let mutable innerLoop = true
let inner_max = i
let mutable j = inner_max
while innerLoop do
let product = i * j
if product < maxPalindrome then
innerLoop <- false
if isPalindrome product && product > maxPalindrome then
maxPalindrome <- product
j <- j - 1
if j < inner_min then
innerLoop <- false
i <- i - 1
if i < outer_min then
outerLoop <- false
maxPalindrome
let euler_4_org() = findLargestPalindrome [ 100 .. 999 ]
let euler_4_v2() = findLargestPalindrome_v2 999 100
let euler_4_v3() = findLargestPalindrome_v3 999 100
And here are the timings:
Solution to Project Euler 4
Org: 906609 in 596.487700 ms
v2 : 906609 in 256.063700 ms
v3 : 906609 in 4.038000 ms
Quite a substantial effect to do the imperative version, even in F#.
Problem 5: Smallest multiple
Even for the final problem you still opted for the brute force, and this took 4 seconds in my environment to solve. After googling a little I found yet another faster imperative solution.
But for this problem I do believe there should be a possibility to find a neater functional solution. Reasoning is that instead of doing the brute force alternative, one could find the prime factors of the different numbers from 1 through 20, and then find the minimum number of factors in order to represent all numbers. In other word, to get 16 you need to have at least 4 times the number 2, but this also gives the 2, 4, 8 and parts of all the even numbers. You need at least 2 times the number 3 to get 3 and 9. And so on.
Added: After a discussion chat related to avoiding mutable, I compiled a new variant using Seq.reduce included in code below.
But here are some faster alternatives:
(** Project Euler 5 : Smallest multiple of 1..20 **********************)
let smallestMultiple top =
let mutable prod = 1
for i in { 1 .. 20 } do
let prevprod = prod
while prod % i <> 0 do
prod <- prod + prevprod
prod
let rec reduce_helper original previous divisor =
if previous % divisor = 0 then
previous
else
reduce_helper original (previous + original) divisor
// Could replace the anonymous fun in the next segment
let smallestMultipleReducer original divisor =
reduce_helper original original divisor
let smallestMultipleUsingReduction top =
seq { 1 .. top }
|> Seq.reduce (fun original divisor ->
reduce_helper original original divisor )
let euler_5_org() = findSmallestMultiple [| 1 .. 20 |]
let euler_5_v2() = smallestMultiple 20
let euler_5_v3a() = smallestMultipleUsingReduction 20
let euler_5_v3b() = smallestMultipleUsingReduction 20
With timings:
Solution to Project Euler 5
Org: 232792560 in 4108.854600 ms
v2 : 232792560 in 0.099500 ms
v3a: 232792560 in 0.700700 ms
v3a: 232792560 in 0.023000 ms
Notice how the timings on v3a and v3b using Seq.reduce are not the same, even though the code is identical. So my timing method, might be a little off, and there seems to happen stuff under the hood optimising code when it's being executed the second time or something like that.
Rewrite of smallestMultiple to avoid mutable
After a little discussion in chat on whether it was possible to avoid the mutable in this solution, I sat down and compiled this variant:
General findings regarding speed and coding style
- It seems it is way faster to use sequences rather than list (or arrays) to fill the pipe lines. So choose wisely to achieve faster run times
- Instead of using
Seq.filter (fun x -> ... ) predefine the predicate or other helper functions to get an order or so faster code. Please verify that this is the case, as it seems there is stuff under the hood which might optimize thing here and there
- For multiline comments use
(* ... *) :-)
- And finally, and this came as a bit of surprise to me: Even though F# is supposedly meant to be fast for handling brute force solution to something like these Project Euler problems, implementing the imperative solution resulted in a speedup from 100 to almost 50000 times your code.
- And as Ethan Bierlein comments, you might want to look into whether to use
List.map and List.collect versus Seq.* as they have slightly different meaning, and different timings and idiomatic consequences.
All code presented here is available at https://repl.it in this code block. Hope this has some value to you, even though most of this review is presenting alternate solutions.
open ...in the middle of your code. \$\endgroup\$