Scala中的Seq和IndexedSeq/LinearSeq有什么区别？

Question

在Scala Collection文档中,这个问题有一些线索:

Trait Seq有两个子线段LinearSeq和IndexedSeq.这些不添加任何新操作,但每个都提供不同的性能特征:线性序列具有有效的头部和尾部操作,而索引序列具有有效的应用,长度和(如果可变的)更新操作.

但这不能解决我何时使用IndexedSeq而不是Seq？我需要一些真实的例子,IndexedSeq或者LinearSeq这些集合比这些更好Seq.

Answer 1

Seq 是超级特征,因此它更通用,它具有所有序列共有的特征,包括线性和索引.

如果您想知道Seq Seq.apply的伴随对象中的方法创建了哪种序列,我们可以看一下实现.

请记住,如果您使用Seq.apply,那么您暗示您只需要一个Seq,而您的代码并不关心它是否为线性或索引

tl; dr答案是:你使用LinearSeq或IndexedSeq当你需要具有一定的性能特征时,你会使用更一般的,Seq当你不关心差异

这是以下的伴侣对象Seq:

object Seq extends SeqFactory[Seq] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]
}

该newBuilder[A]方法是用于构建Seq的方法,因为您可以在Seq.apply方法中验证(在特征上定义GenericCompanion):

def apply[A](elems: A*): CC[A] = {
   if (elems.isEmpty) empty[A]
   else {
     val b = newBuilder[A]
     b ++= elems
     b.result()
   }
 }

现在的问题是:immutable.Seq.newBuilder[A]构建什么？我们来看看,这次是在immutable.Seq伴侣对象上:

object Seq extends SeqFactory[Seq] {
// stuff
  def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer
}

它构建了一个可变的ListBuffer!这是为什么？那是因为a mutable.ListBuffer恰好Builder[A, Seq[A]]也是一个类,集合库使用它来构建新的集合.

实际的输出集合来自这一行(如上所示):

b.result()

那么,什么是返回类型ListBuffer.result()？我们来看看ListBuffer:

// Implementation of abstract method in Builder
def result: List[A] = toList

你走了:这是一个清单.

Seq(1,2,3)返回List[Int]引擎盖,但这里的重点是,如果你使用Seq(),你不需要知道你有什么样的集合,因为你暗示更抽象的界面足以满足你的需求

Answer 2

Seq只是IndexedSeq和LinearSeq的超级特征.Seq是有序列表,而不是Set,它通常是唯一且无序的,而不是Map,它是键值对.
现在是IndexedSeq和LinearSeq.
IndexedSeq子类即Vector,Range,String,都是基于快速索引的访问,通常是快速更新.这是可能的,因为它们在内部使用适合此类数组的数据结构(如在String中)或​​树(实际上是Vector使用的32扇出树...有关详细信息,请参阅此内容)或Range,它只是三个数字. .start,end,step ..从中计算索引是直截了当的.
与此相反,LinearSeq都是基于慢速索引和访问的,并且更新速度很慢.通常因为他们有一种链表的结构.Prepend对所有人来说都很快,即Queue,Stack,List ..但是附加速度非常慢,因为它必须转到内部链表结构的边缘..除了队列使用技巧与它自己的问题.这里描述了诀窍.
从广义上讲,IndexedSeq是那些具有快速索引访问和更新的数据结构,而LinearSeq是那些具有快速前置的数据结构.