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

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

使用包装器的最佳方法是使用标准F#列表LengthList.ofList 创建LengthList,并在使用标准模块中的任何函数之前使用LengthList.toList(或仅使用List)属性List.

但是,它取决于代码的复杂性 - 如果您只需要在几个地方长度,那么将它分开保存并使用元组可能更容易list<'T> * int.

Answer 2

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

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

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

如果你制作了一些非常大的列表,然后没有那么多"改变"(显然从未改变,但我的意思是改变你的域/算法中使用的列表头部的引用集),那么它可能是有意义的只需要将一个字典放到引用列表头*长度元组的一边,并在询问长度时查阅字典(在需要时做真正的工作来处理它们,但缓存结果以便将来询问相同的列表) .

最后,如果你真的在处理一些需要不断更新游戏中的列表并不断查询长度的算法,那么创建你自己的列表类数据(是的,你还需要编写map/filter和any其他).

(一般来说,我认为通常最好在99.99%的时间内使用内置数据结构.在开发算法或需要高度优化的代码的0.01%的时间内,几乎总是你需要放弃内置数据结构(这对于大多数情况来说已经足够了)并使用自定义数据结构来解决您正在处理的确切问题.查看维基百科或Okasaki的"'纯功能数据结构"在这种情况下的想法和启发.但很少去那个案例.)