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

Question

当我们有两个列表时 a和 b ，如何以有效的方式将这两个(顺序无关)连接到一个新列表？

如果 a ::: b，我无法从 Scala API 中弄清楚和 a ++ b是有效的。也许我错过了什么。

Answer 1

在 Scala 2.9 中，::: 的代码(添加到列表中)如下:

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对 List 的操作需要 O(N) :)

另一方面，在 future 的 Scala 版本中，您可能会看到改进的 Vector连接算法，如 this ScalaDays talk 中所示.它 promise 在 O(log N) 时间内解决任务。