F中的缓慢递归递归＃

我有一个F＃函数，它返回跳转n的模式中从0开始的数字列表，选择n，跳过n，选择n ...直到限制。例如，输入2的这个函数将返回[2, 3, 6, 7, 10, 11...]。F中的缓慢递归递归＃

最初我实现此作为如下面的非尾递归函数：

let rec indicesForStep start blockSize maxSize = 
    match start with 
    | i when i > maxSize -> [] 
    | _ -> [for j in start .. ((min (start + blockSize) maxSize) - 1) -> j] @ indicesForStep (start + 2 * blockSize) blockSize maxSize

以为尾递归是可取的，我重新实现它使用的蓄能器列表如下：

let indicesForStepTail start blockSize maxSize = 
    let rec indicesForStepInternal istart accumList = 
     match istart with 
     | i when i > maxSize -> accumList 
     | _ -> indicesForStepInternal (istart + 2 * blockSize) (accumList @ [for j in istart .. ((min (istart + blockSize) maxSize) - 1) -> j]) 
    indicesForStepInternal start []

然而，当我在单声道下用参数1,1和20,000（即应该返回[1, 3, 5, 7...]高达20,000）时，在fsi下运行它时，尾递归版本明显比第一版本慢（12秒与亚秒相比）。

为什么尾递归版本较慢？是因为列表串联？它是一个编译器优化？我有没有实现它尾递归？

我也觉得好像我应该使用高阶函数来做到这一点，但我不确定如何去做。

来源

2011-03-28 Gnat

不幸的是，我没有时间来提供替代的代码，但几个简单的观察：1）它是尾递归，2）名单追加为O（N），因此效率低下。我建议反转（下移）你的列表理解，把它归结为accumList，并在你返回第一个模式匹配之前反转accumList。 – Daniel 2011-03-28 14:37:52

非常感谢大家;这些答案非常有帮助，信息量大，教育程度也很高。 – Gnat 2011-03-29 14:20:06

正如dave指出的那样，问题在于您正在使用@运算符来追加列表。这是比尾递归更重要的性能问题。事实上，尾递归并不会真的加速程序太多（但它使得它在堆栈溢出的大输入上工作）。

您第二个版本较慢的原因是您要将较短的清单（使用[...]生成的清单）附加到较长的清单（accumList）。这比将较长列表附加到较短列表要慢（因为操作需要复制第一个列表）。

let indicesForStepTail start blockSize maxSize = 
    let rec indicesForStepInternal istart accumList = 
     match istart with 
     | i when i > maxSize -> accumList |> List.rev 
     | _ -> 
      let acc = 
      [for j in ((min (istart + blockSize) maxSize) - 1) .. -1 .. istart -> j] 
      @ accumList 
      indicesForStepInternal (istart + 2 * blockSize) acc 
    indicesForStepInternal start []

正如你所看到的，这有短名单（使用[...]生成）：

您可以通过收集在蓄电池中的元素以相反的顺序，然后返回结果之前扭转它修复作为@的第一个参数，并且在我的机器上，它具有与非尾递归版本类似的性能。请注意，[ ... ]理解会以相反的顺序生成元素 - 以便它们可以在最后逆转。

你也可以写了整个事情更加好听使用F＃seq { .. }语法。您可以完全避免使用@运营商，因为它可以让你使用yield!使用yield产生个人elemetns和执行尾递归调用：

let rec indicesForStepSeq start blockSize maxSize = seq { 
    match start with 
    | i when i > maxSize ->() 
    | _ -> 
     for j in start .. ((min (start + blockSize) maxSize) - 1) do 
     yield j 
     yield! indicesForStepSeq (start + 2 * blockSize) blockSize maxSize }

这是我怎么会写。当调用它时，你只需要添加Seq.toList来评估整个惰性序列。这个版本的性能与第一个类似。

编辑随着丹尼尔的更正，Seq版本实际上稍微快一点！

来源

2011-03-28 14:43:45

我相信它需要'让rec'和你的递归调用应该是'indicesForStepSeq'。 – Daniel 2011-03-28 14:56:24

@Daniel：谢谢！你是对的，这个错误总是发生在我身上:-)。现在，'Seq'版本实际上是一个有点快...... – 2011-03-28 15:50:08

为了好奇，我改变了最后一个函数使用一个表的表达式，而不是一个序列的表达，并成为令人难以置信的慢（30秒，'1 20000' ，即比OP的代码慢得多）。任何人都知道为什么发生？ – wmeyer 2011-03-28 16:22:33

这看起来像列表附加是问题。追加基本上是第一个参数大小的O（N）操作。通过累积在左边，这个操作需要O（N^2）时间。

这种通常在功能代码中完成的方式似乎是以相反的顺序累积列表（通过累积在右侧），然后在最后返回列表的反向。

你已经避免了第一个版本的附加问题，但正如你指出的那样，不是尾递归。

在F＃中，解决这个问题的最简单方法可能是序列。它看起来不是很实用，但你可以很容易地创建一个跟随你的模式的无限序列，并使用Seq.take来获得你感兴趣的项目。

来源

2011-03-28 14:36:29

在F＃中，列表类型被实现为单向链表。因此，如果x和y的长度不同，那么x @ y和y @ x会得到不同的性能。这就是为什么你看到了性能的差异。（x @ y）的运行时间为X.length。

// e.g. 
let x = [1;2;3;4] 
let y = [5]

如果你做了X @ y，则X（4元）将被复制到一个新的列表和其下一个内部指针将被设置为现有ÿ列表。如果你做了y @ x，那么y（1个元素）将被复制到一个新列表中，并且其下一个指针将被设置为现有列表x。

我不会使用高阶函数来做到这一点。我会用列表理解来代替。

let indicesForStepTail start blockSize maxSize = 
    [ 
     for block in start .. (blockSize * 2) .. (maxSize - 1) do 
      for i in block .. (block + blockSize - 1) do 
       yield i 
    ]

来源

2011-03-28 14:39:56 gradbot

F中的缓慢递归递归＃

回答

相关问题