scala 中数组和列表的区别

Question

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

Answer 1

不可变结构

Scala

List

是一种不可变的递归数据结构，它是 Scala 中的基本结构，您应该（可能）更多地使用它，而不是

Array

（实际上是 mutable - immutable 模拟

Array

是

IndexedSeq

）。

如果您有 Java 背景，那么明显的相似之处是何时使用

LinkedList

而不是

ArrayList

。前者通常用于仅被遍历过（并且其大小预先未知）的列表，而后者应用于具有已知大小（或最大大小）或快速随机访问的列表很重要。

可变结构

ListBuffer

提供了到

List

的恒定时间转换，如果需要稍后进行转换，这就是使用

ListBuffer

的唯一原因。

scala

Array

应该通过 Java 数组在 JVM 上实现，因此

Array[Int]

可能比

int[]

性能更高（作为

List[Int]

）（它会将其内容装箱，除非您是使用最新版本的 Scala，它具有新的

@specialized

功能）。

但是，我认为 Scala 中

Array

的使用应该保持在最低限度，因为感觉你真的需要知道幕后发生了什么来决定你的数组是否真的会得到所需原语的支持类型，或者可以装箱为包装类型。

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

更好。

Answer 3

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

yield

、

foreach

、

match

等结构的 List。

就性能特征而言，数组在随机访问元素时速度更快，而列表在添加新元素时速度更快。 迭代它们是可比的。