在函数式编程上下文中使用不可变列表获取恒定长度检索时间常数

Question

我目前面临的问题是必须根据给定列表的长度进行计算。必须迭代列表的所有元素才能知道其大小，这是一个很大的性能损失，因为我使用的是相当大的列表。

解决该问题的建议方法是什么？

我想我总是可以将大小值与列表一起携带，这样我就可以事先知道它的大小，而不必在调用站点计算它，但这似乎是一种脆弱的方法。我还可以定义自己的列表类型，其中每个节点都有其列表大小作为属性，但这样我就会失去编程语言的标准列表库提供的杠杆作用。

你们在日常生活中是如何处理这个问题的呢？

我目前正在使用 F#。我知道我可以使用.NET 的可变（数组）列表，这可以解决问题。不过，我对纯粹的不可变函数方法更感兴趣。

Answer 1

内置的 F# 列表类型没有任何长度缓存，并且无法以某种巧妙的方式添加它，因此您需要定义自己的类型。我认为为现有的 F# list 类型编写包装器可能是最好的选择。

这样，您可以避免显式转换 - 当您包装列表时，它实际上不会复制它（如在 svick 的实现中），但包装器可以轻松缓存 Length 属性：

open System.Collections

type LengthList<'T>(list:list<'T>) =
  let length = lazy list.Length
  member x.Length = length.Value
  member x.List = list
  interface IEnumerable with
    member x.GetEnumerator() = (list :> IEnumerable).GetEnumerator()
  interface seq<'T> with  //'
    member x.GetEnumerator() = (list :> seq<_>).GetEnumerator()

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module LengthList =
  let ofList l = LengthList<_>(l)
  let ofSeq s = LengthList<_>(List.ofSeq s)
  let toList (l:LengthList<_>) = l.List
  let length (l:LengthList<_>) = l.Length

最好的工作方式使用包装器的方法是使用 LengthList.ofList 从标准 F# 列表创建 LengthList 并使用 LengthList.toList （或仅使用 LengthList.toList >列表) 属性在使用标准 List 模块中的任何函数之前。

但是，这取决于代码的复杂性 - 如果您只需要几个地方的长度，那么将其单独保存并使用元组 list<'T> 可能会更容易。 * int。

Answer 2

你们在日常生活中如何处理这个问题？

我们不这样做，因为这在日常生活中不是问题。这听起来像是一个在有限领域可能存在的问题。

如果您最近创建了列表，那么您可能已经完成了 O(N) 工作，因此遍历列表来获取其长度可能并不是什么大问题。

如果您正在创建一些非常大的列表，并且这些列表不会“改变”太多（显然永远不会改变，但我的意思是更改对您的域/算法中使用的列表头的引用集），那么可能有意义只需在引用列表头*长度元组的一侧放一本字典，并在询问长度时查阅字典（在需要时进行真正的工作来遍历它们，但缓存结果以供将来询问相同的列表） 。

最后，如果您确实正在处理一些需要不断更新正在运行的列表并不断查询长度的算法，那么创建您自己的类似列表的数据类型（是的，您还需要编写映射/过滤器和任何其他的）。

（一般来说，我认为 99.99% 的时间最好使用内置数据结构。在 0.01% 的时间里，您正在开发需要高度优化的算法或代码，那么几乎总是您需要放弃内置数据结构（对于大多数情况来说已经足够了）并使用旨在解决您正在处理的确切问题的自定义数据结构。请参阅维基百科或冈崎的“纯功能数据”。在这种情况下，结构”用于思想和灵感。但很少去那种情况。）

Answer 3

我不明白为什么携带长度是一种脆弱的方法。尝试这样的事情（Haskell）：

data NList a = NList Int [a]

nNil :: NList [a]
nNil = NList 0 []

nCons :: a -> NList a -> NList a
nCons x (NList n xs) = NList (n+1) (x:xs)

nHead :: NList a -> a
nHead (NList _ (x:_)) = x

nTail :: NList a -> NList a
nTail (NList n (_:xs)) = NList (n-1) xs

convert :: [a] -> NList a
convert xs = NList (length xs) xs

等等。如果这是在库或模块中，您可以通过不导出构造函数 NList 来使其安全（我认为）。

也有可能强制 GHC 记忆 length，但我不确定如何或何时。

Answer 4

在 F# 中，大多数 List 函数都有等效的 Seq 函数。这意味着，您可以实现自己的不可变链表，其中包含每个节点的长度。像这样的东西：

type MyList<'T>(item : Option<'T * MyList<'T>>) =

    let length =
        match item with
        | None -> 0
        | Some (_, tail) -> tail.Length + 1

    member this.Length = length

    member private this.sequence =
        match item with
        | None -> Seq.empty
        | Some (x, tail) ->
            seq {
                yield x
                yield! tail.sequence
            }

    interface seq<'T> with
        member this.GetEnumerator() =
            (this.sequence).GetEnumerator()
        member this.GetEnumerator() =
            (this.sequence :> System.Collections.IEnumerable).GetEnumerator()

module MyList =
    let rec ofList list =
        match list with
        | [] -> MyList None
        | head::tail -> MyList(Some (head, ofList tail))