爲什麼我的遞歸比Array.exists更快？

我是F＃的新手。我試圖瞭解如何在F＃中獲得快速代碼。爲此，我試圖編寫兩種方法（IsPrime1和IsPrime2）進行基準測試。我的代碼是：爲什麼我的遞歸比Array.exists更快？

// 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需要260ms的相同的結果。

這裏發生了什麼事以及如何讓我的代碼更快？

來源

2012-09-12 TapiocaCom

較慢的版本分配一個巨大的數組，然後通過它 - 這是緩慢的 - 你的直接版本有效地將一個數字保存在一個寄存器中 –

此外，你不需要使用'＃light' –

在IsPrime2，你不要構建一個巨大的數組，這樣可以避免分配，顯式遍歷和垃圾收集這個數組。請記住，您在SumOfPrimes中調用了IsPrime1/IsPrime2函數max-1次，因此有很多此類數組的實例。避免創建顯式數據結構可以用作優化技術。

以下是可以在您的代碼上完成的一些小優化。

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-12 06:21:23 pad

它變成了使用可變變量的命令式版本更快。這對我來說有點令人沮喪。不過，謝謝你的回答！ – TapiocaCom

此外，事實證明，IsPrime3是越野車：例如，它返回true爲4。 – TapiocaCom

我修正了這個錯誤。它不會影響'sumOfPrimes'的結果，是嗎？ – pad

的原因速度差，慢的代碼確實是這樣的：

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

wheras快速代碼執行：

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-12 04:06:58

爲什麼我的遞歸比Array.exists更快？

回答

相關問題