什么时候应该在 Scala 中选择 Vector？

作为一般规则，默认使用 Vector。对于几乎所有内容，它都比 List 快，对于大于平凡大小的序列，它的内存效率更高。请参阅此 documentation，了解 Vector 与其他集合相比的相对性能。使用 Vector 有一些缺点。具体来说：

头部的更新比 List 慢（虽然没有你想象的那么快）

Scala 2.10 之前的另一个缺点是对 List 的模式匹配支持更好，但在 2.10 中使用通用的 +: 和 :+ 提取器进行了纠正。

还有一种更抽象的代数方式来解决这个问题：你在概念上有什么样的序列？另外，您在概念上在用它做什么？如果我看到一个返回 Option[A] 的函数，我知道该函数在其域中有一些漏洞（因此是部分漏洞）。我们可以将相同的逻辑应用于集合。

如果我有一个 List[A] 类型的序列，我实际上是在断言两件事。首先，我的算法（和数据）完全是堆栈结构的。其次，我断言我将对这个集合做的唯一事情是完整的 O(n) 遍历。这两个真的是齐头并进。相反，如果我有 Vector[A] 类型的东西，我要断言的唯一是我的数据具有明确定义的顺序和有限长度。因此，Vector 的断言较弱，这导致其更大的灵活性。

---

好吧，如果算法可以单独使用 ::、head 和 tail 实现，那么 List 可以非常快。我最近有一个对象教训，当时我通过生成 List 而不是 Array 击败了 Java 的 split，并且无法用其他任何东西击败它。

但是，List 有一个基本问题：它不适用于并行算法。我无法以有效的方式将 List 拆分为多个段，或将其连接回来。

还有其他类型的集合可以更好地处理并行性 - Vector 就是其中之一。 Vector 还具有很好的局部性 - List 没有 - 这对于某些算法来说可能是一个真正的优势。

因此，考虑到所有因素，Vector 是最佳选择除非您有特定的考虑使其他集合之一更可取 - 例如，如果您想要惰性评估，您可以选择 Stream 并且缓存（Iterator 更快，但不缓存），或者 List 如果算法是通过我提到的操作自然实现的。

顺便说一句，最好使用 Seq 或 IndexedSeq，除非您需要特定的 API（例如 List 的 ::），或者如果您的算法可以使用 GenSeq 或 GenIndexedSeq并行运行。

---

这里的一些陈述令人困惑甚至是错误的，尤其是 Scala 中的 immutable.Vector 类似于 ArrayList 的想法。 List 和 Vector 都是不可变的、持久的（即“获得修改后的副本很便宜”）数据结构。没有合理的默认选择，因为它们可能适用于可变数据结构，但这取决于您的算法在做什么。 List 是一个单链表，而 Vector 是一个 base-32 整数 trie，即它是一种具有 32 度节点的搜索树。使用这种结构，Vector 可以相当快地提供最常见的操作，即在 O(log_32( n))。这适用于头/尾中的前置、附加、更新、随机访问、分解。顺序迭代是线性的。另一方面，列表仅提供线性迭代和恒定时间前置，头/尾分解。其他一切都需要一般的线性时间。

这看起来好像 Vector 在几乎所有情况下都是 List 的一个很好的替代品，但是前置、分解和迭代通常是函数式程序中序列上的关键操作，并且这些操作的常数对于向量来说要高得多，因为到其更复杂的结构。我做了一些测量，所以列表的迭代速度大约是两倍，列表上的 prepend 大约快 100 倍，列表上的头/尾分解大约快 10 倍，并且从可遍历的生成向量大约快 2 倍。 （这可能是因为 Vector 可以在使用构建器构建它时一次分配 32 个元素的数组，而不是一个一个地添加或附加元素）。当然，所有在列表上花费线性时间但在向量上实际上是恒定时间的操作（作为随机访问或追加）在大型列表上将非常缓慢。

那么我们应该使用哪种数据结构呢？基本上，有四种常见情况：

我们只需要通过映射、过滤、折叠等操作来转换序列：基本上没关系，我们应该对我们的算法进行通用编程，甚至可以从接受并行序列中受益。对于顺序操作 List 可能要快一些。但是如果你必须优化，你应该对它进行基准测试。

我们需要大量的随机访问和不同的更新，所以我们应该使用向量，列表会非常慢。

我们以经典的函数方式对列表进行操作，通过递归分解的前置和迭代来构建它们：使用列表，向量将慢 10-100 倍或更多。

我们有一个性能关键算法，它基本上是命令式的，并且对列表进行大量随机访问，例如就地快速排序：在本地使用命令式数据结构，例如 ArrayBuffer，并从中复制数据。

---

对于不可变集合，如果您想要一个序列，您的主要决定是使用 IndexedSeq 还是 LinearSeq，这为性能提供了不同的保证。 IndexedSeq 提供元素的快速随机访问和快速长度操作。 LinearSeq 仅通过 head 提供对第一个元素的快速访问，但也具有快速 tail 操作。 （取自 Seq 文档。）

对于 IndexedSeq，您通常会选择 Vector。 Range 和 WrappedString 也是 IndexedSeq。

对于 LinearSeq，您通常会选择 List 或其惰性等效项 Stream。其他示例是 Queue 和 Stack。

因此，在 Java 术语中，ArrayList 的使用与 Scala 的 Vector 类似，LinkedList 与 Scala 的 List 类似。但在 Scala 中，我倾向于比 Vector 更频繁地使用 List，因为 Scala 对包括遍历序列的函数有更好的支持，比如映射、折叠、迭代等。你会倾向于使用这些函数来操作列表作为整体，而不是随机访问单个元素。

---

在涉及大量随机访问和随机突变的情况下，Vector（或 - 正如 docs 所说 - Seq）似乎是一个很好的折衷方案。这也是 performance characteristics 所建议的。

此外，Vector 类似乎在没有太多数据重复的分布式环境中运行良好，因为不需要对完整对象执行写时复制。 （见：http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures）

---

如果您的编程是不可变的并且需要随机访问，那么 Seq 就是您要走的路（除非您想要一个 Set，而您实际上经常这样做）。否则 List 工作得很好，除了它的操作不能并行化。

如果您不需要不可变的数据结构，请坚持使用 ArrayBuffer，因为它是 Scala 等价于 ArrayList。

---