为什么这个 F# 序列表达式是三次时间而不是线性时间？

Question

我在使用Seq.unfold. 这是我可以想出的最小案例来重现这一点。

let idUnfolder sequence =
   sequence
   |> Seq.tryHead
   |> Option.map (fun head -> (head, Seq.tail sequence))

let seqIdWithUnfold sequence =
   Seq.unfold idUnfolder sequence

该函数seqIdWithUnfold返回给定序列本身。我希望结果序列像Seq.unfoldO(n)那样在线性时间内迭代，Seq.tryHead并且Seq.tail是 O(1)（如果我错了，请纠正我）。然而，据我所知，它具有三次复杂性。

我使用以下函数和一组n值测试了执行时间。

let test n =
   let start = System.DateTime.Now
   Seq.init n id
   |> seqIdWithUnfold
   |> Seq.iter ignore
   let duration = System.DateTime.Now - start
   printfn "%f" duration.TotalSeconds

是什么让这个操作变得复杂？

Answer 1

seq几乎总是O(n)。一个seq又名IEnumerable<T>基本上是：

type Enumerator<'a> = {
    getNext : unit -> 'a option
}

type Seq<'a> = {
    getEnumerator: unit -> Enumerator<'a>
}

每次评估一个序列时，Enumerator都会创建一个新的，它捕获枚举的状态。getNext然后重复调用直到序列终止。

如果您seq在任何时候将 a 替换为with，您可以亲眼看到这一点

source |> Seq.map(fun x -> printfn "Eval %A" x; x)

让我们也显示调用getEnumerator：

let sq  = 
    seq {  
        let mutable ctr = 0
        do printfn "Init  _" 
        while true do
            ctr <- ctr + 1
            printfn "Yield %d" ctr
            yield ctr
        }     

seqIdWithUnfold (sq |> Seq.take 3) |> Seq.toList |> printfn "%A"

还有输出：

Init  _
Yield 1
Init  _
Yield 1
Yield 2
Init  _
Yield 1
Yield 2
Yield 3
Init  _
Yield 1
Yield 2
Yield 3
[1; 2; 3]

这向您展示了经典n(n+1)/2模式。

您可以看到复杂性将包含n + n ^{2 个}项。

如果可以使用列表，您将得到O(n)而不是O(n^2).

如果你真的想要O(1)，使用数组。