为什么迭代通过一个数组的速度比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迭代。

希望这会有帮助