爲什麼迭代通過一個數組的速度比Seq.find

Question

我有一個數組sums，給出了函數f的所有可能的總和。這個函數接受整數（例如1到200之間，但是也適用於1和10000）並將它們轉換爲double。我想將sums作爲數組存儲，因爲我還沒有想出如何在沒有循環的情況下執行我所需要的算法。

下面是我如何生成sums代碼：

let f n k = exp (double(k)/double(n)) - 1.0 


let n = 200 
let maxLimit = int(Math.Round(float(n)*1.5)) 

let FunctionValues = [|1..maxLimit|] |> Array.map (fun k -> f n k) 

let sums = FunctionValues |> Array.map (fun i -> Array.map (fun j -> j + i) FunctionValues) |> Array.concat |> Array.sort 

我發現，我想找到一些整數，當輸入功能附加f，然後將等於值數組sums的某些元素sums。我可以將整數存儲在sums中，但是我發現這破壞了我的記憶。

現在我有兩種算法。算法1使用一個簡單的循環和一個可變的int來存儲我關心的值。它不應該是非常有效的，因爲當它找到所有可能的整數時沒有break語句。儘管Seq是懶惰的，但我發現它更慢（慢10％，或者4200ms比4600ms，n = 10000）。爲什麼是這樣？

算法1：

let mutable a = 0 
let mutable b = 0 
let mutable c = 0 
let mutable d = 0 
for i in 1..maxLimit do 
    for j in i..maxLimit do 
     if sums.[bestI] = f n i + f n j then 
      a <- i 
      b <- j 
     if sums.[bestMid] = f n i + f n j then 
      c <- i 
      d <- j 

算法2：

let findNM x = 
    let seq = {1..maxLimit} |> Seq.map (fun k -> (f n k, k)) 
    let get2nd3rd (a, b, c) = (b, c) 
    seq |> Seq.map (fun (i, n) -> Seq.map (fun (j, m) -> (j + i, n, m)) seq) 
     |> Seq.concat |> Seq.find (fun (i, n, m) -> i = x) 
     |> get2nd3rd 

let digitsBestI = findNM sums.[bestI] 
let digitsBestMid = findNM sums.[bestMid] 

let a = fst digitsBestI 
let b = snd digitsBestI 
let c = fst digitsBestMid 
let d = snd digitsBestMid 

編輯：請注意，數組sums是長度maxLimit*maxLimit不長度n。然後bestI和bestMid是0和maxLimit*maxLimit之間的索引。就這個問題而言，他們可以是該範圍內的任何數字。他們的具體價值並不特別相關。

Answer 1

我伸出的OP代碼位，以剖析其

open System 

let f n k = exp (double(k)/double(n)) - 1.0 

let outer = 200 
let n  = 200 
let maxLimit= int(Math.Round(float(n)*1.5)) 

let FunctionValues = [|1..maxLimit|] |> Array.map (fun k -> f n k) 

let random = System.Random 19740531 

let sums = FunctionValues |> Array.map (fun i -> Array.map (fun j -> j + i) FunctionValues) |> Array.concat |> Array.sort 

let bests = 
    [| for i in [1..outer] -> (random.Next (n, maxLimit*maxLimit), random.Next (n, maxLimit*maxLimit))|] 

let stopWatch = 
    let sw = System.Diagnostics.Stopwatch() 
    sw.Start() 
    sw 

let timeIt (name : string) (a : int*int -> 'T) : unit = 
    let t = stopWatch.ElapsedMilliseconds 
    let v = a (bests.[0]) 
    for i = 1 to (outer - 1) do 
    a bests.[i] |> ignore 
    let d = stopWatch.ElapsedMilliseconds - t 
    printfn "%s, elapsed %d ms, result %A" name d v 

let algo1 (bestI, bestMid) = 
    let mutable a = 0 
    let mutable b = 0 
    let mutable c = 0 
    let mutable d = 0 
    for i in 1..maxLimit do 
    for j in i..maxLimit do 
     if sums.[bestI] = f n i + f n j then 
     a <- i 
     b <- j 
     if sums.[bestMid] = f n i + f n j then 
     c <- i 
     d <- j 

    a,b,c,d 

let algo2 (bestI, bestMid) = 
    let findNM x = 
    let seq = {1..maxLimit} |> Seq.map (fun k -> (f n k, k)) 
    let get2nd3rd (a, b, c) = (b, c) 
    seq |> Seq.map (fun (i, n) -> Seq.map (fun (j, m) -> (j + i, n, m)) seq) 
     |> Seq.concat |> Seq.find (fun (i, n, m) -> i = x) 
     |> get2nd3rd 

    let digitsBestI = findNM sums.[bestI] 
    let digitsBestMid = findNM sums.[bestMid] 

    let a = fst digitsBestI 
    let b = snd digitsBestI 
    let c = fst digitsBestMid 
    let d = snd digitsBestMid 

    a,b,c,d 

let algo3 (bestI, bestMid) = 
    let rec find best i j = 
    if best = f n i + f n j then i, j 
    elif i = maxLimit && j = maxLimit then 0, 0 
    elif j = maxLimit then find best (i + 1) 1 
    else find best i (j + 1) 
    let a, b = find sums.[bestI] 1 1 
    let c, d = find sums.[bestMid] 1 1 
    a, b, c, d 

let algo4 (bestI, bestMid) = 
    let rec findI bestI mid i j = 
    if bestI = f n i + f n j then 
     let x, y = mid 
     i, j, x, y 
    elif i = maxLimit && j = maxLimit then 0, 0, 0, 0 
    elif j = maxLimit then findI bestI mid (i + 1) 1 
    else findI bestI mid i (j + 1) 

    let rec findMid ii bestMid i j = 
    if bestMid = f n i + f n j then 
     let x, y = ii 
     x, y, i, j 
    elif i = maxLimit && j = maxLimit then 0, 0, 0, 0 
    elif j = maxLimit then findMid ii bestMid (i + 1) 1 
    else findMid ii bestMid i (j + 1) 

    let rec find bestI bestMid i j = 
    if bestI = f n i + f n j then findMid (i, j) bestMid i j 
    elif bestMid = f n i + f n j then findI bestI (i, j) i j 
    elif i = maxLimit && j = maxLimit then 0, 0, 0, 0 
    elif j = maxLimit then find bestI bestMid (i + 1) 1 
    else find bestI bestMid i (j + 1) 

    find sums.[bestI] sums.[bestMid] 1 1 

[<EntryPoint>] 
let main argv = 

    timeIt "algo1" algo1 
    timeIt "algo2" algo2 
    timeIt "algo3" algo3 
    timeIt "algo4" algo4 

    0 

我的機器上測試結果：

algo1, elapsed 438 ms, result (162, 268, 13, 135) 
algo2, elapsed 1012 ms, result (162, 268, 13, 135) 
algo3, elapsed 348 ms, result (162, 268, 13, 135) 
algo4, elapsed 322 ms, result (162, 268, 13, 135) 

algo1使用天真for loop實施。 algo2使用依賴於Seq.find的更精確的算法。稍後我會描述algo3和algo4。

OP想知道爲什麼天真algo1表現得更好，甚至它更多的工作比是根據各地懶Seq（實質上是一個IEnumerable<>）的algo2。

答案是Seq抽象引入開銷並阻止有用的優化發生。

我通常會求助於查看生成的IL代碼，以瞭解發生了什麼事情（有很多很好的.NET反編譯器，比如ILSpy）。

讓我們來看看algo1（反編譯C＃），然後

// Program 
public static Tuple<int, int, int, int> algo1(int bestI, int bestMid) 
{ 
    int a = 0; 
    int b = 0; 
    int c = 0; 
    int d = 0; 
    int i = 1; 
    int maxLimit = Program.maxLimit; 
    if (maxLimit >= i) 
    { 
    do 
    { 
     int j = i; 
     int maxLimit2 = Program.maxLimit; 
     if (maxLimit2 >= j) 
     { 
     do 
     { 
      if (Program.sums[bestI] == Math.Exp((double)i/(double)200) - 1.0 + (Math.Exp((double)j/(double)200) - 1.0)) 
      { 
      a = i; 
      b = j; 
      } 
      if (Program.sums[bestMid] == Math.Exp((double)i/(double)200) - 1.0 + (Math.Exp((double)j/(double)200) - 1.0)) 
      { 
      c = i; 
      d = j; 
      } 
      j++; 
     } 
     while (j != maxLimit2 + 1); 
     } 
     i++; 
    } 
    while (i != maxLimit + 1); 
    } 
    return new Tuple<int, int, int, int>(a, b, c, d); 
} 

algo1擴展到一個有效的while loop。另外內聯f。 JITter很容易從這裏創建高效的機器代碼。

當我們在看algo2拆包完整結構是太多這個職位讓我專注於findNM

internal static Tuple<int, int> findNM@48(double x) 
{ 
    IEnumerable<Tuple<double, int>> seq = SeqModule.Map<int, Tuple<double, int>>(new Program.seq@49(), Operators.OperatorIntrinsics.RangeInt32(1, 1, Program.maxLimit)); 
    FSharpTypeFunc get2nd3rd = new Program.get2nd3rd@50-1(); 
    Tuple<double, int, int> tupledArg = SeqModule.Find<Tuple<double, int, int>>(new Program.findNM@52-1(x), SeqModule.Concat<IEnumerable<Tuple<double, int, int>>, Tuple<double, int, int>>(SeqModule.Map<Tuple<double, int>, IEnumerable<Tuple<double, int, int>>>(new Program.findNM@51-2(seq), seq))); 
    FSharpFunc<Tuple<double, int, int>, Tuple<int, int>> fSharpFunc = (FSharpFunc<Tuple<double, int, int>, Tuple<int, int>>)((FSharpTypeFunc)((FSharpTypeFunc)get2nd3rd.Specialize<double>()).Specialize<int>()).Specialize<int>(); 
    return Program.get2nd3rd@50<double, int, int>(tupledArg); 
} 

我們可以看到，它需要傳遞實現IEnumerable<>多個對象和函數對象的創建更高階的功能，如Seq.find。儘管JITter原則上有可能內聯循環，但由於時間限制和內存原因，它很可能不會。這意味着每個對函數對象的調用都是虛擬調用，虛擬調用相當昂貴（提示：檢查機器代碼）。因爲虛擬調用可能會做任何事情，從而阻止優化，如使用SIMD指令。

該OP指出，F＃循環表達式缺少break/continue構造，在編寫高效的for loops時非常有用。然而，F＃不會支持它，因爲如果你編寫一個尾遞歸函數F＃將它展開成一個高效的循環，它使用break/continue提前退出。

algo3是使用尾遞歸實現algo2的示例。反彙編代碼是這樣的：

internal static Tuple<int, int> find@66(double best, int i, int j) 
{ 
    while (best != Math.Exp((double)i/(double)200) - 1.0 + (Math.Exp((double)j/(double)200) - 1.0)) 
    { 
    if (i == Program.maxLimit && j == Program.maxLimit) 
    { 
     return new Tuple<int, int>(0, 0); 
    } 
    if (j == Program.maxLimit) 
    { 
     double arg_6F_0 = best; 
     int arg_6D_0 = i + 1; 
     j = 1; 
     i = arg_6D_0; 
     best = arg_6F_0; 
    } 
    else 
    { 
     double arg_7F_0 = best; 
     int arg_7D_0 = i; 
     j++; 
     i = arg_7D_0; 
     best = arg_7F_0; 
    } 
    } 
    return new Tuple<int, int>(i, j); 
} 

這讓我們寫成語功能的代碼，但同時避免堆棧溢出得到很好的表現。

在我實現良好尾遞歸如何在F＃實現我試圖寫高效while迴路與可變邏輯在while測試表達式。爲了人類的利益，現在代碼被廢除。

algo4是一個優化的版本，它只有一次兩個bestMid和bestI很像algo1但algo4退出早期如果可以的sums迭代。

希望這會有幫助