F# 中的慢尾递归

Question

我有一个 F# 函数，它返回从 0 开始的数字列表，格式为“跳过 n、选择 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 []

但是，当我在 Mono 下使用参数 1、1 和 20,000 在 fsi 中运行此函数时（即应返回 [1, 3, 5, 7...] 最多 20,000），尾递归版本明显慢于第一个版本（12 秒与亚秒相比）。

为什么尾递归版本较慢？是因为列表串联的原因吗？是编译器优化吗？我实际上是尾递归实现的吗？

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

Answer 1

正如戴夫指出的，问题在于您使用 @ 运算符来附加列表。这是比尾递归更重要的性能问题。事实上，尾递归并没有真正使程序加速太多（但它使它可以在堆栈溢出的大输入上工作）。

第二个版本较慢的原因是您将较短的列表（使用 [...] 生成的列表）附加到较长的列表 (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! 执行尾递归调用：

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 即可评估整个惰性序列。该版本的性能与第一个版本类似。

编辑 经过 Daniel 的修正，Seq 版本实际上稍微快一些！

Answer 2

在 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
    ]

Answer 3

这看起来像是列表附加是问题所在。追加基本上是对第一个参数的大小进行 O(N) 操作。通过在左侧累加，此操作需要 O(N^2) 时间。

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

您拥有的第一个版本避免了附加问题，但正如您所指出的，不是尾递归。

在 F# 中，解决此问题的最简单方法可能是使用序列。它看起来不太实用，但您可以轻松地按照您的模式创建无限序列，并使用 Seq.take 来获取您感兴趣的项目。