7

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

a ::: b我无法从 Scala API中找出a ++ b是否有效。也许我错过了什么。

4

1 回答 1

9

在 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 talk中所展示的。它承诺在 O(log N) 时间内解决任务。

于 2012-07-19T20:10:28.863 回答