F#中的慢尾递归

Question

我有一个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 []

但是,当我在Mono下使用参数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 { .. }语法更好地编写整个内容.您可以@完全避免使用运算符,因为它允许您使用以下内容生成单个elemetns 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版本实际上稍快一点!

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

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

这通常在功能代码中完成的方式似乎是以相反的顺序累积列表(通过在右侧累积),然后在结束时返回列表的反向.

您拥有的第一个版本避免了追加问题,但正如您所指出的那样,不是尾递归.

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