数组和List之间的区别在Scala中

在什么情况下,我应该使用数组(缓冲区)和列表(缓冲区)。 我所知道的只有一个区别是数组是非variables的,列表是协变的。 但是性能和其他一些特性呢?

不可变的结构

Scala List是一个不可变的recursion数据结构,它是Scala中的一个基本结构,您应该(可能)比使用Array (实际上是可变的Array不变模拟IndexedSeq )更多地使用它。

如果您来自Java背景,那么明显的并行是在ArrayList上使用LinkedList 。 前者一般用于仅经历过的列表(而且其大小不是预先知道的),而后者应该用于具有已知大小(或最大大小)或者快速随机访问是重要的列表。

可变结构

ListBuffer提供了一个List的常量转换,如果需要这样的后续转换的话, ListBuffer是唯一的原因。

一个scala Array应该在JVM上由一个Java数组实现,因此一个Array[Int]可能比List[Int]更高效(作为int[] )具有新的@specializedfunction的最新版本的Scala)。

不过,我认为在Scala中使用Array应该保持在最低限度,因为它觉得你真的需要知道底层是怎么回事,以决定你的数组是否真的被所需的基本types所支持,或者可能被装箱作为包装types。

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

虽然Array[A]实际上是一个Java数组,但List[A]是一个不可变的数据结构,它可以是Nil (空列表),也可以是一个对(A, List[A])

性能差异

  Array List Access the ith element O(1) O(i) Discard the ith element O(n) O(i) Insert an element at i O(n) O(i) Reverse O(n) O(n) Concatenate (length m,n) O(n+m) O(n) Calculate the length O(1) O(n) 

记忆差异

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

所以除非你需要快速的随机访问或者需要对批量元素进行计数,否则ListArray更好。

一个数组是可变的,这意味着你可以改变每个索引的值,而List(默认)是不可变的,这意味着每次你做一个修改时都会创build一个新的列表。 在大多数情况下,使用不可变数据types是一种更“function”的风格,您应该尝试使用带有yieldforeachmatch等结构的List。

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