何时应选择Scala中的Vector?
何时应选择Scala中的Vector?
看起来Vector
来参加Scala集合派对比较晚,所有有影响力的博客文章都已经发布了。
在Java中,ArrayList
是默认的集合 - 我可能会使用LinkedList
,但只有在经过算法思考并且足够关心优化时才会使用。在Scala中,我应该将Vector
作为我的默认Seq
,还是尝试计算何时实际上使用List
更合适?
嗯,如果算法能够仅用::
,head
和tail
来实现,List
可以非常快。最近我就有一个很好的例子,用生成List
代替Array
可以击败Java的split
,用其他方法都达不到这个效果。
然而,List
存在一个根本性问题:无法与并行算法一起使用。我无法以高效的方式将List
分成多个段或重新连接它。
还有其他类型的集合可以更好地处理并行性 - Vector
就是其中之一。 Vector
也具有很好的局部性 - List
没有 - 这可以成为一些算法的真正优点。
所以,总体考虑,除非您具有使其他集合更合适的特定考虑,否则Vector
是最佳选择 - 例如,如果您想进行惰性评估和缓存(Iterator
更快但不会缓存),或者算法自然使用我提到的操作,则可以选择List
。
顺便说一下,除非您需要特定的API(例如List
的::
),否则最好使用Seq
或IndexedSeq
,或者如果您的算法可以并行运行,则使用GenSeq
或GenIndexedSeq
。
通常情况下,使用Vector
是默认选择。对于几乎所有的操作,它比List
更快,并且对于大于平凡大小的序列来说更节省内存。请参阅这篇相对于其他集合的Vector
性能的文档。使用Vector
也有一些缺点,具体如下:\n\n
- \n
- 在头部进行更新比
List
慢(虽然不像你想象中的那么慢)
\n
\n\n在Scala 2.10之前,使用List
支持模式匹配的效果更好,但在2.10中使用了广义的+:
和:+
提取器来补充这一缺陷。\n\n还有一种更抽象、代数的方法来解决这个问题:你实际上拥有什么样的序列?你实际上是在干什么?如果我看到一个返回Option[A]
的函数,我知道这个函数在其域中有一些空缺(因此是部分的)。我们可以将相同的逻辑应用于集合。\n\n如果我有一个类型为List[A]
的序列,我实际上断言了两件事。首先,我的算法(和数据)完全是堆栈结构。其次,我断言我对这个集合唯一要做的事情就是全面的O(n)遍历。这两个事情实际上是相辅相成的。相反,如果我有一个类型为Vector[A]
的序列,我断言的唯一事情是我的数据有一个明确定义的顺序和一个有限的长度。因此,使用Vector
的断言较弱,这导致它更具有灵活性。