Scala List与ListBuffer中concat和append的性能比较

Question

我想了解List和ListBuffer在追加和连接方面的性能差异

var myList = List(1, 2)
myList = myList ::: List(4, 5)
myList = myList :+ 6

var myMutableList = ListBuffer(1, 2)
myMutableList = myMutableList ++ ListBuffer(4, 5)
myMutableList += 6

我的理解是

myList = myList ::: List(4, 5)

将为新列表分配空间，并遍历要连接的原始myList和列表，并将所有元素附加到新列表

myList = myList :+ 6

将为新列表分配空间，并遍历原始myList，并将原始项和新项附加到新列表

myMutableList = myMutableList ++ ListBuffer(4, 5)

将，如果有足够的空间，只是附加到旧的列表，但如果没有足够的空间，将做同样的事情myList = myList ::: List(4, 5)

也一样

myMutableList += 6

所以ListBuffer在非索引追加和concat中都更有效?

Answer 1

首先，我想解决这个(恕我直言)完全误导的语法

myNewList: List[Int] = myList ::: List(4, 5)

来自Scala文档:

/**
* Adds the elements of a given list in front of this list.
* @param prefix The list elements to prepend.
* @tparam B Type of elements in the prefix (a subtype or equal type to A)
* @tparam A Type of elements in the suffix
* @return a list resulting from the concatenation of the given list prefix and this list.
*/
def:::[B >: A](prefix: List[B]): List[B]

为了澄清这种语法，这里有一个使用后缀表示法(如您所拥有的)与普通中缀表示法(将函数应用于对象)比较的示例

// Postfix on left, equivalent to infix on right
List(1, 2) ::: List(3, 4) = List(3, 4).:::(List(1, 2)) = List(1, 2, 3, 4)

你在上面真正写的是:

myNewList: List[Int] = List(4, 5).:::(myList)

在语义上，append是它看起来要做的事情，但是使用中缀表示法，我们看到前缀是该函数的实参，而不是后缀。

对于concat的性能，list和listbuffer具有相同的签名:

final def concat[B >: A](suffix: IterableOnce[B]): List[B] // Or ListBuffer[B] for `ListBuffer`

因此concat可能使用各自类型的追加操作来实现，对于Lists，这是线性的;对于ListBuffer，这是常数。然而，对于小列表/缓冲区，这种差异可能是任意的。

Answer 2

myList ::: List(4, 5)将反转myList，然后开始将反转myList的每个元素前缀到List(4, 5)中。因此，这是共享/重用以前的List(4, 5)
编辑:好吧，我上面说的是如果标准库List是真正不可变的会发生什么，但它实际上是可变的(只是在标准库之外不可见)。因此，stdlib利用这一点来创建一个新的::，其中myList的头部和List(4, 5)的尾部，然后它将开始修改新列表的尾部，以不断添加myList的剩余元素-无论如何，最终结果是相同的复杂性和List(4, 5)共享的事实;就快!

myList :+ 6确实需要从头开始重新分配一个新的列表，并且效率非常低。

myMutableList ++ ListBuffer(4, 5)这可能是一个坏主意，因为使用可变集合的想法是改变它，你可能想这样做:

val myMutableList = ListBuffer(1, 2)
myMutableList ++= ListBuffer(4, 5)
myMutableList += 6

在这种情况下，++=和+=都是非常有效的，因为它们只是在ListBuffer

中的内部List中添加了前置。