Euler Project Problem 14 in F# - An exercise in optimization
The coding “coding-experiments” blog presents two alterative solutions to the “Euler Project Problem 14” (http://projecteuler.net/print.php?id=14):
http://coding-experiments.blogspot.com/2008/03/projecteulernet-problem-14-csharp-vs.html
His F# solution is around 55 times slower in than the C# version, the implication being that while F# is elegant, it’s also slow. My problem with this conjecture is that that the implementation of the F# version is considerably different to the implementation of the C# version. So lets have a look at the two different version, first the F#:
let seq_length n =
n |>
Seq.unfold(fun x ->
match x with
| x when x = 0L -> None
| x when x = 1L -> Some((1L,0L))
| x when x%2L=0L -> Some((x,x/2L))
| _ -> Some((x,3L*x + 1L))
) |> Seq.length
[for i in 1L..1000000L -> (i, seq_length i)]
|> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al) )
|> (fun (x,y) -> x ) |> print_any
Then the C#:
class Euler14 {
static long CountTerms(long x, ref long[] terms) {
long tc = 1;
long k = x;
while (k != 1) {
tc++;
k = (k % 2 == 0) ? k / 2 : 3 * k + 1;
if (k <= x) {
if (terms[k] > 0) {
terms[x] = terms[k] + tc;
return terms[x];
}
}
}
terms[x] = tc;
return terms[x];
}
static long LongestSeq() {
long max = 1000000;
long[] termcount = new long[max + 1];
long tcmax = 0;
long c = 0;
long ix = 0;
for (int i = 1; i <= max; i++) {
c = CountTerms(i, ref termcount); if (c > tcmax) {
tcmax = c;
ix = i;
}
}
return ix;
}
static void Main(string[] args) {
Console.WriteLine(LongestSeq());
}
}
The C# executes in around 0.7 second on my machine, while the F# as given takes a whopping 29 seconds. The first thing to notice about the F# implementation is that we calculate and store the entire sequence then we calculate its length by walking the sequence again. Since we’re not interested in the sequence – just its length we can cut the time down by calculating the length straight off, this cuts us down to about 8 seconds:
let rec seq_length x n =
match x with
| x when x = 0L -> (n + 1)
| x when x = 1L -> seq_length 0L (n + 1)
| x when x%2L=0L ->seq_length (x/2L) (n + 1)
| _ -> seq_length (3L*x + 1L) (n + 1)
let rec loop i imax n =
let n' = seq_length i 0
let imax, n = if n' > n then i, n' else imax, n
if i < 1000000L then loop (i + 1L) imax n else imax
print_any (loop 1L 0L 0)
So even though that’s a big improvement, still no cigar. If we look more closely at the C# version, we see it plays a clever trick, it uses an array to memorise the lengths of sequences, so once we find a number we’ve already calculated we’ve no need to calculate it again. The simplest way to implement memorization is to use a System.Collections.Generic.Dicrionary:
#light
open System.Collections.Generic
let dict = new Dictionary< int64, int >()
let seq_length x n =
let updateDict n =
dict.Add(x, n)
n
let rec seq_length x n =
if dict.ContainsKey(x) then
updateDict (n + dict.[x])
else
match x with
| x when x = 0L -> updateDict (n + 1)
| x when x = 1L -> seq_length 0L (n + 1)
| x when x%2L=0L ->seq_length (x/2L) (n + 1)
| _ -> seq_length (3L*x + 1L) (n + 1)
seq_length x n
let rec loop i imax n =
let n'= seq_length i 0
let imax, n = if n' > n then i, n' else imax, n
if i < 1000000L then loop (i + 1L) imax n else imax
print_any (loop 1L 0L 0)
This takes us down to around 2.2 seconds – better but still a little way off the C# version. A bit educated guess work leads us to think this version is probably slower because, a) we used a dictionary instead of an array (although much move convent to use), b) we access tuples inside a loop cause objects to be created and we need to access properties (call methods) to retrieve the values. Cutting this out we arrive at an algorithm that is pretty much the same as the C#:
#light
let transform n = if n%2L = 0L then n/2L else n*3L+1L
let rec seq_length x k n memo =
if k = 1L then
memo.(x) <- (n+1)
(n+1)
else if k < 1000000L then
let foo = memo.[int k]
if foo > 0 then
memo.(x) <- foo + n
foo + n
else
seq_length x (transform k) (n+1) memo
else seq_length x (transform k) (n+1) memo
let rec loop i imax n memo =
let n' = seq_length i (int64 i) 0 memo
if i < 1000000 then
if n' > n then loop (i+1) i n' memo else loop (i+1) imax n memo
else imax
print_any (loop 1 1 0 (Array.create 1000001 0))
This executes in around 1 second on my machine. If we add the compile flags “--standalone -O3” we see the execution time go down to 0.85 seconds, I feel it may be possible to get closer that this but I have run out of ideas (for now). So while 0.15 seconds is significantly slower that the C# version (~21%) it’s pretty acceptable margin, and the advantages we are still considerable shorter, 23 lines versus ~60 lines.
So there you go, I think we can still safely claim that F# has a performance profile similar to C#. Having we lost some of our elegance by using arrays for memorisation, well probably, but for my money we’re still a lot more elegant and understandable that the C# version.
Thanks to Lars Nilsson, who gave me plenty of ideas to help with the optimization!