performance - F#中的慢尾递归

Question

我有一个 F# 函数，它以跳过 n、选择 n、跳过 n、选择 n... 的模式返回从 0 开始的数字列表。例如，输入 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 下的 fsi 中使用参数 1、1 和 20,000(即应该返回 [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版本其实稍微快一点!