连接列表的有效方法是什么？

def :::[B >: A](prefix: List[B]): List[B] =
  if (isEmpty) prefix
  else (new ListBuffer[B] ++= prefix).prependToList(this)

而且更通用,因为它采用CanBuildFrom参数,即它可以返回与List不同的集合类型：

override def ++[B >: A,That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A],B,That]): That = {
  val b = bf(this)
  if (b.isInstanceOf[ListBuffer[_]]) (this ::: that.seq.toList).asInstanceOf[That]
  else super.++(that)
}

因此,如果您的返回类型是List,则两者执行相同的操作.

ListBuffer是一种聪明的机制,因为它可以用作变异构建器,但最终被toList方法“消耗”.那么(新的ListBuffer [B] =前缀).prependToList(this)的作用是,首先按顺序添加前缀中的所有元素(在示例a中),取O(| a |)时间.然后它调用prependToList,这是一个恒定时间操作(接收器或b,不需要拆开).因此,总时间为O(| a |).

另一方面,正如pst指出的那样,我们有反向_ ::::

def reverse_:::[B >: A](prefix: List[B]): List[B] = {
  var these: List[B] = this
  var pres = prefix
  while (!pres.isEmpty) {
    these = pres.head :: these
    pres = pres.tail
  }
  these
}

因此,使用reverse _ ::: b,这又需要O(| a |),因此与其他两个方法相比效率更高或更低(尽管对于小的列表大小,您可以节省创建中间ListBuffer的开销).

换句话说,如果您了解a和b的相对大小,则应确保前缀是两个列表中较小的一个.如果您没有这方面的知识,那么您无能为力,因为List上的大小操作需要O(N):)

另一方面,在未来的Scala版本中,您可能会看到改进的Vector级联算法,如this ScalaDays talk所示.它承诺在O(log N)时间内解决任务.