157

在什么情况下我应该使用 Array(Buffer) 和 List(Buffer)。我知道的唯一区别是数组是不变的,而列表是协变的。但是性能和其他一些特性呢?

4

3 回答 3

165

不可变结构

ScalaList是一个不可变的递归数据结构,它是 Scala 中的一个基本结构,您应该(可能)使用它比使用它更多Array(它实际上是可变的 - is 的不可变模拟)。ArrayIndexedSeq

如果您来自 Java 背景,那么明显的相似之处是何时使用LinkedListover ArrayList。前者通常用于只遍历过的列表(并且其大小预先不知道),而后者应该用于具有已知大小(或最大大小)或快速随机访问很重要的列表。

可变结构

ListBuffer提供到 a 的恒定时间转换,如果需要稍后进行转换List,则仅使用该转换。ListBuffer

scalaArray应该由 Java 数组在 JVM 上实现,因此 aArray[Int]可能int[]比 a 性能更高(作为 an )List[Int](它将包装其内容,除非您使用具有新@specialized功能的最新版本的 Scala) .

但是,我认为ArrayScala 中 s 的使用应该保持在最低限度,因为感觉就像你真的需要知道幕后发生了什么来决定你的数组是否真的将由所需的原始类型支持,或者可能被装箱为包装类型。

于 2010-04-26T11:17:41.260 回答
136

除了已经发布的答案之外,这里还有一些细节。

虽然 anArray[A]实际上是一个 Java 数组,但 aList[A]是一个不可变的数据结构,它要么是Nil(空列表)要么由一个 pair 组成(A, List[A])

性能差异

                          Array  List
Access the ith element    θ(1)   θ(i)
Delete the ith element    θ(n)   θ(i)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)
Count the elements        θ(1)   θ(n)

Memory differences

                          Array  List
Get the first i elements  θ(i)   θ(i)
Drop the first i elements θ(n-i) θ(1)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)

So unless you need rapid random access, need to count elements, or for some reason you need destructive updates, a List is better than an Array.

于 2010-04-26T12:44:22.500 回答
19

Array 是可变的,这意味着您可以更改每个索引的值,而 List(默认情况下)是不可变的,这意味着每次进行修改时都会创建一个新列表。在大多数情况下,使用不可变数据类型是一种更“功能性”的风格,您可能应该尝试使用带有 , 等结构yieldforeachList match

对于性能特征,随机访问元素时 Array 更快,而在预先(添加)新元素时 List 更快。迭代它们是可比的。

于 2010-04-26T11:19:55.953 回答