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

Question

当我们有两个列表a和b,一个人如何可以连接这两个(顺序是不相关)到一个新的列表以有效的方式？

如果a ::: b并且a ++ b效率很高,我无法从Scala API 中找到答案.也许我错过了什么.

Answer 1

在Scala 2.9中,:::(prepend to list)的代码如下:

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方法"消耗" .那么(new ListBuffer[B] ++= prefix).prependToList(this),首先按顺序添加prefix(在示例中a)所有元素,取O(| a |)时间.然后调用prependToList,这是一个恒定时间操作(接收器,或者b,不需要拆开).因此,总时间为O(| a |).

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

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
}

因此a reverse_::: b,这又需要O(| a |),因此其他两种方法的效率没有或多或少(尽管对于小的列表大小,您可以节省中间ListBuffer创建的开销).

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

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