| The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? |
Ok, so here it is. Lets have fun with F#:
euler14.fs
Elegant, slow version of solution-> ~20 lines; ~10 seconds.
Now lets try C#:
euler14.cs
Ugly, fast version of solution -> ~0.18 second; ~60 lines.
Conclusion:
F# solutions can be done in more elegant/less code way, but in contrary it is slower that C#
counterpart. Also C# solutions can be written in fast way, but needs more code and attention.
F# solution was by factor 55 slower than C# solution, but also code was by factor of 3 shorter than C# counterpart. So if you want elegancy/generics power - take F#; and if you want only perfomance- take C#.
P.S. There is a way in F# to code (using mutable keyword) very very ugly like in C#, but i`ve not
suggest using it on F#,- why to code ugly in F# if you can grab C# instead ?? :-)
10 comments:
You can considerable improve the preformance of your F# code with out resorting to use the mutable keyword. This code preforms is a factor of 10 slower that the C#, still not perfect but better that a factor of 55 slower:
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)
It was pointed out to me that the C# version used memorization were as the my F# version didn't once correct the F# version execution time is less that a second and it's still half the number of lines:
#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)
The following F# code is only about 30% slower than the C# version, but still shorter and more readable.
Some notes:
- I would expect the F# optimizer to improve over the next months, so that this F# implementation will probably catch up performance-wise.
- Comparing the original two implementations really is comparing apples with oranges.
- F# is not Haskell. You are allowed to use imperative code constructs and you should do so if that makes your code easier to understand or orders of magnitude faster.
- The readability of the F# code suffers somewhat from the need to make all conversions between int and int64 explicit. This is the price you pay for code inference.
- Interestingly the JIT manages to replace the integer division/ remainder operation with appropriate bit operations even though long is signed. On the other hand, if one replaces all long/int64 with ulongs/uint64 and thus makes the signlessness explicit, the braindead JIT inserts integer division operations instead.
- The ref qualification of the array argument in your C# code is superfluous.
#light
open System
open System.Diagnostics
let max = 1000000L
let countTerms x (terms: int64[]) =
let rec count c = function
| k when k = 1L -> c
| k when k <= x && terms.[int k] > 0L -> terms.[int k] + c
| k when k % 2L = 0L -> count (c + 1L) (k/2L)
| k -> count (c + 1L) (3L*k + 1L)
count 1L (int64 x)
let longestSequence () =
let termcount = Array.zero_create (int max + 1)
let mutable tcmax, ix = int64 0, 0
for i in 1 to int max do
let c = countTerms (int64 i) termcount
termcount.[i] <- c
if c > tcmax then
tcmax <- c
ix <- i
ix
let main () =
let sw = new Stopwatch()
sw.Start()
let result = longestSequence()
sw.Stop()
printf "Result: %i, Runtime: %ims" result sw.ElapsedMilliseconds
System.Console.ReadKey(false)
main ()
The following F# code is 3x shorter and 40% faster than your C#:
let rec inside (a : _ array) n =
if n<=1L || a.[int n]>0s then a.[int n] else
let p =
if n &&& 1L = 0L then inside a (n >>> 1) else
let n = 3L*n + 1L
if n < int64 a.Length then inside a n else outside a n
a.[int n] <- 1s + p
1s + p
and outside (a : _ array) n =
let n = if n &&& 1L = 0L then n >>> 1 else 3L*n + 1L
1s + if n < int64 a.Length then inside a n else outside a n
let euler14 n =
let a = Array.create (n+1) 0s
let a = Array.init (n+1) (fun n -> inside a (int64 n))
let i = Array.find_index (Array.fold1_left max a |> (=)) a
i, a.[i]
euler14 1000000
Flying Frog Consultancy Ltd. said...
The following F# code is 3x shorter and 40% faster than your C#
Ok it may be faster if you say so, but...acctually your code is ugly/not elegant at all and more C#-like than F#-like, because:
1. You are using .NET arrays instead of F# specifics - lists and/or sequences.
2. Acctually your code is mutable, because you are modifying array elements.
3. You are doing a lot mumbo-jumbo stuff like operations on bits.
So for these reasons this code is much more similar to C# and as such, is unworthy in a beautiful F# world, IMHO. I will repeat- if you need to do so for code optimization - please grab C# and not pollute nice F# language :-)
If possible please investigate an example that uses the performance of multi-core CPU's using ParallelFX: multi-processing extensions for .NET Framework.
Ref.:
http://weblogs.asp.net/esanchez/archive/2007/11/30/parallelfx-multi-processing-extensions-for-net-framework.aspx
Thanks,
art
Well.. by replace one c# line to
(guess which line..):
k = ((k & 0x1) == 0) ? (k >> 1) : ((k << 1) + k) + 1;
I squeezed another 20% performance improvement out of the ugly version...
Sorry. I do not agree that the F# Solution is elegant. And being allowed to put a lot of code in few lines does not make the code easier to write (or read). Implementing the F# algoritm in C# should take around 15 lines (not much different from the propossed ~20).
I assign no merit on making the F# version to be fast sacrificing the much elogiated elegance (that was hardly there anyway).
If you like a language, there is no need to defend it to the extent of producing unconsistent comparisons.
Personaly I like C and the required code can be written in 2 lines and will execute a 1000 times faster.
You might like to look at my solution to Problem 14 which uses a Functional approach in C#, and has an elegant approach to memoize the calculations.
"Carlos said...
I do not agree that the F# Solution is elegant."
You are missing one important thing - ELEGANCY is subjective term, dependant on human`s opinion.
I think any thing in the world can be elegant to some people and in the same time - not elegant to the other people. So there is no need to agree or disagree on some language elegance. That is just a matter of taste.
"Carlos said...
If you like a language, there is no need to defend it to the extent of producing unconsistent comparisons."
First -
I like C# AND F# AND Python :-)
Second -
I think you are wrong. If I like a language (or any thing in the world) - it`s my right to show my taste in ANY format I wish - be it
'unconsistent comparisons' or whaterver else.
Third -
As you unnoticed yet - this is just my personal BLOG. In my opinion - blogs by definition can`t be very reliable knowledge source. Reliable knowledge sources (more or less) are Wikipedia / Britanica / other encyclopedia AND/OR scientific literature in general. So you are looking for 'consistent comparisons' not in the right place.
Post a Comment