F#中的尾递归速度缓慢

Question

F#中的尾递归速度缓慢

4

我有一个返回从0开始按照跳n、选n的模式排列的数字列表的F#函数，直到达到限制。例如，输入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运行它时（即应该返回[1, 3, 5, 7...]，直到20,000），尾递归版本比第一版本慢得多（需要12秒，而不是亚秒级）。

为什么尾递归版本更慢呢？是因为列表连接吗？还是编译器优化？我是否实际上已经实现了尾递归？

我也觉得我应该使用高阶函数来完成这个任务，但我不确定如何去做。

- Gnat

1

很抱歉，我没有时间提供替代代码，但是有几个快速观察：1）它是尾递归的；2）列表append是O(n)，因此效率低下。我建议将您的列表推导式反转（步进下降），将其连接到accumList中，并在第一次模式匹配内返回之前反转accumList。 - Daniel

非常感谢大家，这些答案非常有帮助、信息量丰富和富有教育意义。 - Gnat

3个回答

7

在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个元素）将被复制到一个新列表中，并且它的内部 next 指针将被设置为现有的 y 列表。如果你执行 y @ x，则 y（1个元素）将被复制到一个新列表中，并且它的 next 指针将被设置为现有的 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
    ]

- gradbot

6

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

函数式代码通常使用在右侧累积列表，然后在最后返回列表的反向累积方式来解决这个问题。

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

在F#中，解决这个问题可能最简单的方法是使用序列。虽然它看起来不太像函数式编程，但你可以轻松地创建一个按照你的模式遵循的无限序列，并使用Seq.take获取你感兴趣的项目。

- dave jones

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tomas Petricek · Accepted Answer

正如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!执行尾递归调用：

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以评估整个lazy序列。这个版本的性能与第一个版本相似。编辑根据Daniel的更正，Seq 版本实际上略快！