連接列表的有效方法是什麼？

當我們有兩個列表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

連接列表的有效方法是什麼？

回答

相關問題