如果我将一个序列转换为一个数组并将其视为一个序列，我得到的长度是 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.ofArray returns 仅实现 IEnumerator<T> 的 ArrayEnumerator 因此调用 Seq.length 将需要枚举整个序列以获得长度。

直接在数组上调用 Seq.length 将使用底层 Length 属性，因为它会对数组类型、列表和 ICollection<T> 的实例进行动态类型检查。

Answer 2

如果序列实际上是数组类型，那么它将简单地转换回数组以确定 Seq.length 中的数组。您可以在 length 函数 here:

的实现中看到这一点

[<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 function 从 ArrayEnumerator:

创建匿名 IEnumerable

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

如果我将一个序列转换为一个数组并将其视为一个序列，我得到的长度是 O(1) 吗？

If I convert a sequence to an array and treat it as a sequence, do I get O(1) on length?

arrays

f#

seq