我应该什么时候在Scala中selectVector?

看来Vector已经迟到了Scala的collections派对,所有有影响力的博客文章都已经离开了。

在Java中ArrayList是默认的集合 – 我可能会使用LinkedList但只有当我想通过一个algorithm和照顾足够优化。 在Scala中,我应该使用Vector作为默认的Seq ,还是试图在List实际上更合适?

一般来说,默认使用Vector 。 对于几乎所有的东西都比List更快,而对于大小不一的大小的序列来说,它的效率更高。 请参阅此文档的Vector相对于其他集合的相对性能。 使用Vector有一些缺点。 特别:

  • 头部更新比List更慢(尽pipe不像你想象的那么多)

在Scala 2.10之前的另一个缺点是List模式匹配支持比较好,但是在2.10中用+::+提取器进行了纠正。

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

如果我有一个List[A]types的序列,我有效地断言了两件事情。 首先,我的algorithm(和数据)是完全堆栈结构的。 其次,我断言我要做的唯一的事情就是完整的O(n)遍历。 这两个真的是携手共进。 相反,如果我有Vector[A]types的东西,我唯一断言的是我的数据有一个明确的顺序和有限的长度。 因此, Vector的断言较弱,这导致了更大的灵活性。

那么,如果algorithm只能用::headtail来实现, List可以非常快。 最近我有一个对象的教训,当我通过生成一个List而不是一个Array来打败Java的split ,并且无法用其他任何东西来打败它。

但是, List有一个基本的问题:它不适用于并行algorithm。 我无法以有效的方式将List拆分为多个段,或将其连接在一起。

还有其他types的集合可以更好地处理并行性,而Vector就是其中之一。 Vector也具有很好的局部性 – 哪些List没有 – 对某些algorithm来说这是一个真正的优点。

所以,考虑到所有的因素, 除非你有特定的考虑因素, 否则 Vector是最好的select – 例如,如果你想懒惰的评估和caching( Iterator更快但不caching) ,或者如果algorithm是自然地用我提到的操作来实现的话。

顺便说一下,如果您的algorithm可以并行运行,则最好使用SeqIndexedSeq除非您需要特定的API(如List 's :: GenSeq ,甚至GenSeqGenIndexedSeq

对于不可变的集合,如果你想要一个序列,你的主要决定是使用一个IndexedSeq还是一个LinearSeq ,这会给性能提供不同的保证。 IndexedSeq提供元素的快速随机访问和快速的长度操作。 LinearSeq只能通过head快速访问第一个元素,但也具有快速tail操作。 (摘自Seq文档。)

对于IndexedSeq您通常会select一个VectorRange s和WrappedString也是IndexedSeqs。

对于LinearSeq您通常会select一个List或其惰性等效的Stream 。 其他的例子有QueueStack

所以在Java方面, ArrayList与Scala的Vector类似,而LinkedList类似于Scala的List 。 但是在Scala中,我倾向于使用List比Vector更频繁,因为Scala对包含遍历序列的函数(如映射,折叠,迭代等等)有更好的支持。您将倾向于使用这些函数来将列表操作为整体,而不是随机访问个别元素。

这里的一些陈述是混乱的,甚至是错误的,特别是不可变的思想。Scala中的向量就像一个ArrayList。 列表和向量都是不可变的,持久的(即“获得修改后的副本”)数据结构。 没有合理的默认select,因为它们可能是可变的数据结构,但它取决于你的algorithm在做什么。 List是一个单向链表,Vector是一个32位的基本整数树,即它是一种32度节点的search树。使用这个结构,Vector可以提供最常见的操作,比如在O(log_32 N))。 这适用于prepend,追加,更新,随机访问,头/尾分解。 顺序迭代是线性的。 列表另一方面只是提供线性迭代和恒定时间前置,在头部/尾部分解。 一切都需要一般的线性时间。

这可能看起来好像在几乎所有情况下,Vector都是List的好替代品,但是前置,分解和迭代通常是function程序中序列的关键操作,并且这些操作的常量对于向量的(高得多)到它更复杂的结构。 我做了一些测量,所以迭代大约是列表的两倍,prepend在列表上大约快100倍,head / tail中的分解大约是列表的10倍,从vector遍历的速度大约是vector的2倍。 (这可能是因为当你使用一个构build器来构build它时,Vector可以一次分配32个元素的数组,而不是一个一个的预先添加或附加元素)。 当然,所有在列表上花费线性时间但在vector上有效地保持恒定时间(作为随机访问或附加)的操作在大型列表上将过于缓慢。

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

  • 我们只需要通过映射,filter,折叠等操作来转换序列:基本上没关系,我们应该一般地编程我们的algorithm,甚至可以从接受并行序列中受益。 对于顺序操作List可能要快一点。 但是如果你需要优化,你应该对它进行基准testing。
  • 我们需要大量的随机访问和不同的更新,所以我们应该使用向量,列表将会非常慢。
  • 我们以经典的函数方式对列表进行操作,通过recursion分解来迭代构build它们:使用列表,向量将会减慢10-100倍或更多。
  • 我们有一个性能关键的algorithm,基本上是必要的,并且在列表上做了大量的随机访问,像就地快速sorting:在本地使用命令式数据结构,例如ArrayBuffer,并将数据从中复制到数据结构中。

在涉及大量随机访问和随机突变的情况下, Vector (或者像文档所说的Seq )似乎是一个很好的折衷。 这也是性能特征所暗示的。

另外, Vector类似乎在分布式环境中很好地工作,没有太多的数据重复,因为不需要为整个对象进行写时复制。 (请参阅: http : //akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures )

如果你的程序是不可变的,需要随机访问,Seq就是要走的路(除非你需要一个你经常实际做的Set)。 否则,List运行良好,除了它的操作不能并行。

如果您不需要不可变的数据结构,请使用ArrayBuffer,因为它是与ArrayList等效的Scala。