1

我对 F# 很陌生。我试图了解如何在 F# 中获得快速代码。为此，我尝试编写两种方法 (IsPrime1和IsPrime2) 进行基准测试。我的代码是：

// 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需要 760 毫秒，而IsPrime2相同的结果需要 260 毫秒。

这里发生了什么以及如何使我的代码更快？

4

2 回答 2

3

在IsPrime2中，您不会构造一个巨大的数组，因此您可以避免分配、显式遍历和垃圾收集该数组。请记住，您调用了 IsPrime1/IsPrime2 函数max-1次，SumOfPrimes因此此类数组的实例很多。避免创建显式数据结构可以用作优化技术。

以下是可以对您的代码进行的一些小的优化。

1) 要检查 中的除数hasDivisors，您只需检查sqrt(n)并跳过所有偶数。如果没有找到除数，则检查的数字是素数。

let rec hasDivisor2 n d =
    match d with
    | x when x <= int(sqrt(float n)) -> (n % x = 0) || (hasDivisor2 n (d+2)) 
    | _ -> false

let IsPrime3 n =
    n = 2 || (n%2 <> 0 && not (hasDivisor2 n 3))

2）对于SumOfPrimes，您可以消除中间数组并跳过所有偶数（无论如何它们都不能是素数）。

let sumOfPrimes isPrime max = 
    [|2..max|] |> Array.filter isPrime|> Array.sum

let sumOfPrimes2 isPrime max = 
    let mutable sum = 2L
    for i in 3..2..max do
        if isPrime i then
            sum <- sum + int64 i
    sum

3) 我做了一个小改动，以便将 isPrime 作为参数传递。这样，您可以更轻松地测量您的代码：

let time fn =
    let sw = new System.Diagnostics.Stopwatch()
    sw.Start()
    let f = fn()
    sw.Stop()
    printfn "Time taken: %.2f s" <| (float sw.ElapsedMilliseconds)/1000.0
    f

let maxVal = 200000

let p2 = time (fun () -> sumOfPrimes IsPrime2 maxVal)
let p3 = time (fun () -> sumOfPrimes2 IsPrime3 maxVal)

新sumOfPrimes2功能IsPrime3非常快。在我的机器上用了 0.05 秒，maxVal = 200000而原始版本用了 7.45 秒。

于 2012-09-12T06:21:23.703 回答
0

速度差异的原因是慢代码做了这样的事情：

if n%a.[1] = 0 || n%a.[2]=0 ...

而快速代码可以：

if n%2=0 || n%(2+1)=0 ...

在快速的情况下，我们不需要去记忆来获得下一个因素。我们还避免了在快速情况下构建数组

这是我构建素数表的通用非常快速的 F# 代码（来自此答案：https ://stackoverflow.com/a/12014908/124259 ）：

#time "on"

let limit = 1000000
//returns an array of all the primes up to limit
let table =
    let table = Array.create limit true //use bools in the table to save on memory
    let tlimit = int (sqrt (float limit)) //max test no for table, ints should be fine
    let mutable curfactor = 1;
    while curfactor < tlimit-2 do
        curfactor <- curfactor+2
        if table.[curfactor]  then //simple optimisation
            let mutable v = curfactor*2
            while v < limit do
                table.[v] <- false
                v <- v + curfactor
    let out = Array.create (100000) 0 //this needs to be greater than pi(limit)
    let mutable idx = 1
    out.[0]<-2
    let mutable curx=1
    while curx < limit-2 do
        curx <- curx + 2
        if table.[curx] then
            out.[idx]<-curx
            idx <- idx+1
    out
于 2012-09-12T04:06:58.123 回答