F# why my recursion is faster than Seq.exists?
Posted
by
user38397
on Stack Overflow
See other posts from Stack Overflow
or by user38397
Published on 2012-09-12T03:24:31Z
Indexed on
2012/09/12
3:38 UTC
Read the original article
Hit count: 121
I am pretty new to F#. I'm trying to understand how I can get a fast code in F#. For this, I tried to write two methods (IsPrime1 and IsPrime2) for benchmarking. My code is:
// Learn more about F# at http://fsharp.net
open System
open System.Diagnostics
#light
let isDivisible n d = n % d = 0
let IsPrime1 n =
Array.init (n-2) ((+) 2) |> Array.exists (isDivisible n) |> not
let rec hasDivisor n d =
match d with
| x when x < n -> (n % x = 0) || (hasDivisor n (d+1))
| _ -> false
let IsPrime2 n =
hasDivisor n 2 |> not
let SumOfPrimes max =
[|2..max|] |> Array.filter IsPrime1 |> Array.sum
let maxVal = 20000
let s = new Stopwatch()
s.Start()
let valOfSum = SumOfPrimes maxVal
s.Stop()
Console.WriteLine valOfSum
Console.WriteLine("IsPrime1: {0}", s.ElapsedMilliseconds)
//////////////////////////////////
s.Reset()
s.Start()
let SumOfPrimes2 max =
[|2..max|] |> Array.filter IsPrime2 |> Array.sum
let valOfSum2 = SumOfPrimes2 maxVal
s.Stop()
Console.WriteLine valOfSum2
Console.WriteLine("IsPrime2: {0}", s.ElapsedMilliseconds)
Console.ReadKey()
IsPrime1 takes 760 ms while IsPrime2 takes 260ms for the same result. What's going on here and how I can make my code even faster?
© Stack Overflow or respective owner