为什么此 F# 序列表达式是立方时间而不是线性时间？

seq几乎总是. aka 本质上是：O(n)seqIEnumerable<T>

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

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

每次计算序列时，都会创建一个捕获枚举状态的新序列。 然后重复调用，直到序列终止。EnumeratorgetNext

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

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² 项。

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

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

正如菲利普·卡特（Philip Carter）在评论中提到的是O（n）。Seq.tail

我不确定为什么 F# 列表是不可接受的，F# 列表是单链表，因此您可以获得恒定时间尾。如果你需要接受任何序列作为你的签名，只需在展开之前转换为列表，它仍然使它成为 O（n），你展示的这个例子无论如何都不能懒惰，除非你真的不需要尾巴。

let seqIdWithUnfold sequence =
       sequence
           |> Seq.toList
           |> List.unfold idUnfolder 
           |> List.toSeq

您的处理示例仍适用于 List 模块

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

但我认为它看起来会更干净一些

let idUnfolder =
    function | [] -> None
             | h::t -> Some(h, t);

Benchamarks

|          Method |        Mean |     Error |    StdDev |
|---------------- |------------:|----------:|----------:|
|        Original | 4,683.88 us | 36.462 us | 34.106 us |
|  ListConversion |    15.63 us |  0.202 us |  0.179 us |

// * Hints *
Outliers
  Benchmarkem.ListConversion: Default -> 1 outlier  was  removed (16.53 us)

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 us   : 1 Microsecond (0.000001 sec)