如果我将序列转换为数组并将其视为序列，则长度是否为O（1）？

Question

我想知道当序列转换为数组然后从此以后再次视为序列时，是否会得到特殊待遇。

let sq = seq { for i in 0 .. 10 do yield i }
let arr = Seq.toArray sq
let len = Array.length arr      // O(1)
let sq2 = arr |> Seq.ofArray

// from converted seq
let len2 = Seq.length sq2       // O(n)???

// or direct:
let len2 = Seq.length arr       // O(n)???

出于同样的原因，F＃是否足够聪明，Seq.toArray arr可以简单地创建数组的副本，单独保留数组（而不创建副本），还是使用枚举器遍历每个项目？

换句话说，F＃中的序列是否还以某种方式记得它们的内部结构是数组？

我问这个问题，因为在昂贵的序列上，您可能需要多次输入长度，并且一次对其进行评估将是有益的。我可以创建一个记住长度的特定序列类型，也可以使用已经存在的魔术。

Answer 1

如果序列实际上是数组类型，则将其简单地转换回数组以确定其中的数组Seq.length。您可以在以下length函数的实现中看到这一点：

[<CompiledName("Length")>]
let length (source : seq<'T>)    = 
    checkNonNull "source" source
    match source with 
    | :? ('T[]) as a -> a.Length
    | :? ('T list) as a -> a.Length
    | :? ICollection<'T> as a -> a.Count
    | _ -> 
        use e = source.GetEnumerator() 
        let mutable state = 0 
        while e.MoveNext() do
            state <-  state + 1;
        state

如果将其放在FSI中，您可以看到此行为：

let arr = [|1..40000000|];;

使用Array.length：

Array.length arr;;
Real: 00:00:00.000, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 40000000

使用Seq.length：

Seq.length arr;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 40000000

如果您使用的Seq.ofArray是专门隐藏基础类型信息，则创建一个新的枚举器，逐步遍历数组中的每个元素。

这可能是一个有用的行为，因为它可以防止您的API使用者偷偷摸摸地seq<'T>回退'T[]，从而允许该使用者对您（API设计者）期望暴露的不变观点进行某些更改。

这种信息隐藏的缺点是您无法转换回数组，因此枚举变得非常慢：

Seq.length <| Seq.ofArray arr;;
Real: 00:00:00.148, CPU: 00:00:00.140, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 40000000

Seq.ofArray使用的mkSeq功能只是IEnumerable从创建匿名ArrayEnumerator：

let mkSeq f = 
    { new IEnumerable<'U> with 
          member x.GetEnumerator() = f()
      interface IEnumerable with 
          member x.GetEnumerator() = (f() :> IEnumerator) }