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

当我们有两个列表a和b时，如何以有效的方式将这两个列表（顺序不相关）连接到一个新列表？连接列表的有效方法是什么？

我找不出Scala API，如果a ::: b和a ++ b是有效的。也许我错过了什么。

2012-07-19 John Threepwood

它可能是'reverse _ :::'（对于immutable.List），因为这只需要从左到右......在任何情况下[偷看源代码]（https://github.com） /scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala） – 2012-07-19 20:09:12

scala的连接方法非常高效。连接不会创建完整的新列表。相反，它需要两个列表并将第一个列表的最后一个元素引用到第二个元素的第一个元素。 – 2012-07-20 05:46:00

在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 |）。

在otherhand，如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的相对大小，你应该确保前缀为小两个列表。如果你没有知识，没有什么可以做，因为在List的size操作需要O（N）:)

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

来源

2012-07-19 20:10:28

既然顺序“无所谓”，那么'reverse _ :::'怎么办？我会想象这会是'O（l）'，其中'l'是左边列表中元素的数量。 – 2012-07-19 20:12:01

所有版本对我来说都是O（a），假设它们都是列表。由于不变性，左侧部分将被复制，右侧部分将由于不变性而被共享。 – Kaito 2012-07-19 20:34:01

@Kaito - 我正在查看这个，看着'prependToList'。我认为你是对的，在那里。将更正答案。 – 2012-07-19 20:49:34

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

回答

相关问题