为什么这个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.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

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

我不知道为什么F#列表是不可接受的，F#列表是单链接列表，所以您可以得到固定的时间尾。如果您需要接受任何序列，因为您的签名只是在展开之前转换成一个列表，它仍然使它成为O(n)，除非您真的不需要尾巴，否则这个示例无论如何也不能懒惰。

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

您的处理示例仍然适用于列表模块。

 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)