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

Question

似乎VectorScala收集派对迟到了,所有有影响力的博客帖子已经离开了.

在Java中ArrayList是默认的集合 - 我可能会使用,LinkedList但只有当我通过算法并且足够小心地进行优化时才会使用.在Scala中,我应该使用Vector我的默认设置Seq,还是尝试在List实际上更合适时使用？

Answer 1

作为一般规则,默认使用Vector.这是比快List的几乎一切,更多的内存效率比平凡的较大尺寸的序列.请参阅此文档,了解Vector与其他集合相比的相对性能.这有一些缺点Vector.特别:

• 头部的更新速度慢于List(虽然没有你想象的那么多)

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

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

如果我有一个类型的序列List[A],我有效地断言了两件事.首先,我的算法(和数据)完全是堆栈结构的.其次,我断言我将要对这个集合做的唯一事情是完整的O(n)遍历.这两者真的是相辅相成的.相反,如果我有类型Vector[A]的东西,我唯一断言的是我的数据有一个明确定义的顺序和有限的长度.因此,断言较弱Vector,这导致其更大的灵活性.

Answer 2

嗯,List如果算法可以单独实现::,head并且可以非常快tail.我最近有一个对象课,当我split通过生成一个List而不是一个来击败Java时Array,并且无法用其他任何东西击败它.

但是,List有一个基本问题:它不适用于并行算法.我不能List以有效的方式将一个段拆分成多个段,或者将它连接回来.

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

因此,考虑到所有事情,Vector是最好的选择,除非您有特定的考虑因素使其他集合之一更受欢迎 - 例如,您可以选择Stream是否需要延迟评估和缓存(Iterator更快但不缓存),或者List如果算法自然是用我提到的操作实现的.

顺便说一句,最好使用Seq或IndexedSeq除非你想要一个特定的API(如Lists ::),甚至GenSeq或者GenIndexedSeq你的算法可以并行运行.

Answer 3

对于不可变集合,如果需要序列,则主要决定是使用a IndexedSeq还是a LinearSeq,它们对性能提供不同的保证.IndexedSeq提供元素的快速随机访问和快速长度操作.LinearSeq仅提供对第一个元素的快速访问head,但也具有快速tail操作.(取自Seq文档.)

对于IndexedSeq你通常会选择一个Vector.Ranges和WrappedStrings也是IndexedSeqs.

对于LinearSeq你通常会选择一个List或它的懒惰等价物Stream.其他例子是Queues和Stacks.

因此,在Java术语,ArrayList使用同样Scala的Vector,并且LinkedList同样Scala的List.但是在Scala中,我倾向于比Vector更频繁地使用List,因为Scala对包含遍历序列的函数(如映射,折叠,迭代等)有更好的支持.您将倾向于使用这些函数来操作列表作为整体而不是随机访问个别元素.

Answer 4

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

在几乎所有情况下,这可能看起来好像Vector是List的一个很好的替代品,但是前置,分解和迭代通常是函数程序中序列的关键操作,并且这些操作的常数对于矢量到期而言(更高)它的结构比较复杂.我进行了一些测量,因此迭代速度大约是列表的两倍,前缀在列表上快了大约100倍,头/尾的分解在列表上快了大约10倍,而从可遍历的生成大约是向量的2倍.(这可能是因为Vector在使用构建器构建它时可以一次分配32个元素的数组,而不是逐个添加或附加元素).当然,所有在列表上采用线性时间但在向量上有效恒定时间(如随机访问或追加)的操作在大型列表上会非常慢.

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

• 我们只需要通过map,filter,fold等操作来转换序列:基本上无关紧要,我们应该对我们的算法进行一般编程,甚至可以从接受并行序列中获益.对于顺序操作,List可能会更快一些.但是如果你必须进行优化,你应该对它进
• 我们需要大量的随机访问和不同的更新,所以我们应该使用vector,list会非常慢.
• 我们以经典的函数方式对列表进行操作,通过递归分解和迭代来构建它们:使用列表,向量将慢10-100或更多.
• 我们有一个性能关键的算法,基本上是必不可少的,并且在列表上进行大量的随机访问,比如快速排序:在本地使用命令式数据结构,例如ArrayBuffer,并从中复制数据.