1

私はF＃にかなり慣れていません。F# で高速なコードを取得する方法を理解しようとしています。このために、ベンチマーク用の2 つのメソッド (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()

IsPrime1IsPrime2同じ結果に260ミリ秒かかるのに対し、760ミリ秒かかります。

ここで何が起こっているのか、コードをさらに高速化するにはどうすればよいですか?

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 に答える