F＃中的慢尾递归
我有一个F＃函数，它返回跳转n模式中从0开始的数字列表，选择n，跳过n，选择n ...直到限制。 例如，输入2的该功能将返回[2, 3, 6, 7, 10, 11...] 。
最初我将它作为一个非尾递归函数实现，如下所示：
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秒相比，亚秒）。
为什么尾递归版本较慢？ 是因为列表串联？ 它是一个编译器优化？ 我有没有实现它尾递归？
我也觉得我应该使用更高级的函数来做到这一点，但我不确定如何去做。
正如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来产生单个elemet并使用yield执行尾递归调用yield! ：
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版本实际上稍快一点！
在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列表。 如果你做了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
]
这看起来像附加列表是问题。 追加基本上是第一个参数大小的O（N）操作。 通过累积在左边，这个操作需要O（N ^ 2）时间。
通常在功能代码中完成的方式似乎是以相反的顺序累积列表（通过累积在右侧），然后在最后返回列表的反向。
你有第一个版本避免了追加问题，但正如你所指出的，不是尾递归。
在F＃中，解决这个问题的最简单方法可能是使用序列。 它看起来功能不是很好，但你可以轻松创建一个跟随你的模式的无限序列，并使用Seq.take获取你感兴趣的项目。