Scala中Array和List的区别

Question

什么情况下我应该使用Array(Buffer)和List(Buffer)？我知道的唯一区别是数组是非变体的，而列表是协变的。但是对于性能和其他特性呢？

- Jeriho

Answer 1

不可变结构

Scala的List是一种不可变的递归数据结构，是Scala中如此基本的结构，以至于您应该（可能）比使用Array更多地使用它（实际上Array是可变的 - 其不可变对应物是IndexedSeq）。

如果您来自Java背景，则明显的对应关系是何时使用LinkedList而非ArrayList。前者通常用于仅遍历的列表（其大小事先未知），而后者应用于具有已知大小（或最大大小）或需要快速随机访问的列表。

可变结构

ListBuffer提供了常数时间转换为List，这就是仅仅因为需要进行此类后续转换而使用ListBuffer的原因。

Scala的Array应该由Java数组在JVM上实现，因此Array[Int]作为int[] 可能会更高效，而List[Int]将封装其内容（除非您正在使用最新版本的Scala，其中有新的@specialized特性）。

然而，我认为在Scala中应该尽可能少地使用Array，因为这感觉上您真的需要知道内部发生了什么才能决定您的数组是否确实将被所需的原始类型支持，或者可能被封装为包装器类型。

- oxbow_lakes

---

Arrays的“equals”定义是它们引用同一个数组。另请参见https://dev59.com/8XA75IYBdhLWcg3wlqKh和https://dev59.com/GXE95IYBdhLWcg3wDpgG。 - oluies

Answer 2

除了已经发布的答案外，这里提供一些具体内容。

尽管 Array[A] 字面上是 Java 数组，但 List[A] 是一个不可变数据结构，它要么是 Nil（空列表），要么由一对 (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)

内存差异

                          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)

所以，除非你需要快速随机访问、需要计算元素个数或者因为某些原因需要破坏性更新，List 比 Array 更好。

- Apocalisp

---

这考虑了在必要时复制列表和数组。请注意，诸如 drop 的操作永远不需要复制未被删除的列表部分。例如，(x::xs).drop(1) 正是 xs，而不是 xs 的“副本”。 - Apocalisp

列表的反转和连接复杂度很糟糕...在C语言中，你可以很容易地获得O(1)的复杂度。我相信如果在Scala中正确实现，也可以做到同样的效果 >.< - A T

这些渐近分析与Scala毫无关系。在C中，相同的数据结构将完全具有相同的速度，只是常数因子可能不同。 - Apocalisp

@Apocalisp 你有参考资料或者是在什么条件下得出这个信息的吗？ - Phil

@Phil 这些是渐近分析，而不是测量。它们在所有情况下都是正确的。 - Apocalisp

Answer 3

数组是可变的，这意味着您可以更改每个索引的值，而列表（默认情况下）是不可变的，这意味着每次修改时都会创建一个新列表。在大多数情况下，使用不可变数据类型更具“函数式”风格，您应该尝试使用包括yield、foreach、match等结构的列表。

在性能方面，当随机访问元素时，数组更快，而当添加新元素时，列表更快。对它们进行迭代是可比较的。

- leonm

---

@leonm - 抱歉，我以为OP只是在询问*Buffer类，现在我意识到他们也在询问“普通”的类！ - oxbow_lakes

通常情况下，将元素附加到ArrayBuffer比将元素前置到List（或向ListBuffer添加元素）更快，因为列表需要创建包装器对象，而ArrayBuffer仅需要将对象复制（平均约两次）到新数组中。两个副本通常比一个对象创建更快，因此ArrayBuffer附加通常优于List前置。 - Rex Kerr

数组在迭代时比列表快得多，这是因为缓存的原因。 - Bin