为什么这个 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 returns 给定序列本身。我希望生成的序列在线性时间内迭代，因为 Seq.unfold 是 O(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 替换为

，您可以自己查看

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

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

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

Answer 2

正如 Philip Carter 在评论中提到的那样 Seq.tail 是 O(n)。

我不确定为什么 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);

基准

|          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)

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

Why is this F# sequence expression cubic time instead of linear?

algorithm

debugging

f#

sequence

time-complexity