Scala中scala.collection.mutable
包下的MutableList
和ListBuffer
类有什么区别?在什么情况下会使用其中之一?
我的使用场景是有一个线性序列,我可以高效地删除第一个元素、添加前缀和后缀。什么是最好的数据结构?
Scala中scala.collection.mutable
包下的MutableList
和ListBuffer
类有什么区别?在什么情况下会使用其中之一?
我的使用场景是有一个线性序列,我可以高效地删除第一个元素、添加前缀和后缀。什么是最好的数据结构?
ListBuffer
内部使用 Nil
和 ::
来构建一个不可变的 List
,并允许常数时间删除第一个和最后一个元素。为此,它保持对列表的第一个和最后一个元素的指针,并且实际上可以改变(否则不可变的)::
类的头部和尾部(通过 ::
的 private[scala] var
成员变量的巧妙技巧)。它的 toList
方法也能够以常数时间返回正常的不可变的 List
,因为它可以直接返回内部维护的数据结构。它也是不可变 List
的默认构建器(因此可以合理地预期它具有常数时间追加)。如果你调用了 toList
,然后又向缓冲区追加一个元素,那么它需要与当前缓冲区中的元素数量成线性关系的时间来重新创建一个新的结构,因为它不能再更改导出的列表了。
MutableList
内部使用 LinkedList
,一个(公开的,不像 ::
)可变链表实现,它知道它的元素和后继(就像 ::
)。MutableList
也保持对第一个和最后一个元素的指针,但是 toList
返回的时间复杂度是线性的,因为结果的 List
是从 LinkedList
中构建的。因此,在导出 List
后,它不需要重新初始化缓冲区。ListBuffer
和 MutableList
是等价的。如果你想在某个时候导出它们的内部列表,那么问问自己在哪里需要开销:当你导出列表时,并且在你继续改变缓冲区时没有开销(那么选择 MutableList
),还是仅在你再次改变缓冲区时有开销,而导出时没有开销(那么选择 ListBuffer
)。我猜测在2.8的集合重构中,MutableList
先于 ListBuffer
和整个 Builder
系统出现。实际上,MutableList
主要有用于在 collection.mutable
包内部使用:它有一个private[mutable] def toLinkedList
方法,以常数时间返回结果,因此可以高效地用作维护 LinkedList
的所有结构的委托构建器。
因此,我也建议使用ListBuffer
,因为它未来可能会得到更多关注和优化,而“纯可变”结构如 MutableList
和 LinkedList
则不然。
MutableList
和ListBuffer
在此方面没有区别。 MutableList
的文档说它被用作Stack
和Queue
的基类,所以也许ListBuffer
更适合从用户角度看作官方类?Buffer
是一个 trait,它具有常量级别的追加和插入,而大多数其他操作都是线性的。我猜测实现了 Buffer
的类 ListBuffer
具有常量级别的删除第一个元素的时间复杂度。ListBuffer
。首先,让我们了解一下Scala中的几个相关类型
List
- 一个不可变集合。它是一种递归实现,即列表的一个实例有两个主要元素:头部和尾部,其中尾部引用另一个List
。
List[T]
head: T
tail: List[T] //recursive
LinkedList
- 一种可变的集合,由一系列链接的节点组成,每个节点包含一个值和一个指向下一个节点的指针。
Node[T]
value: T
next: Node[T] //sequential
LinkedList[T]
first: Node[T]
列表(List)是一种函数式数据结构(不可变性),相对于在命令式语言中更为常见的链表(LinkedList)。
现在,让我们看看:
ListBuffer
- 由List
支持的可变缓冲区实现。
MutableList
- 基于LinkedList实现(如果它被命名为LinkedListBuffer
,那将更为自说明)。
但是,如果您从MutableList
请求一个List
,那么它必须将现有的线性表示转换为递归表示,这需要O(n),正如@Jean-Philippe Pellet所指出的那样。但是,如果您从MutableList
请求一个Seq
,则复杂度为O(1)。
因此,我认为选择取决于您代码的具体情况和个人偏好。尽管我怀疑有更多的List
和ListBuffer
存在。
a :: as
返回一个新的序列,其中元素a
被添加到现有序列as
的前面。 - Jean-Philippe Pellet