Performance of concat and append in Scala List vs ListBuffer-CodePudding

I want to understand the difference in performance in append and concat between List and 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

My understanding is that

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

will allocate space for a new list and iterate through the original myList and list to be concatenated and append all element to the new list

myList = myList :  6

will allocate space for a new list and iterate through the original myList and append the original item and the new item to the new list

myMutableList = myMutableList    ListBuffer(4, 5)

will, if there is enough space just append to the old list, but if there is not enough space will do the same thing as myList = myList ::: List(4, 5)

same with

myMutableList  = 6

so ListBuffer is more efficient in both non indexed append and concat?

CodePudding user response：

myList ::: List(4, 5) will reverse myList and then will start appending each element of the reversed myList into List(4, 5). Thus, this is sharing / reusing the previous List(4, 5)

myList : 6 will indeed need to reallocate a new list from scratch and is very inefficient.

myMutableList ListBuffer(4, 5) this is probably a bad idea since the idea of using a mutable collection is to mutate it, you probably want to do this instead:

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

In this case, both = and = are very efficient since they are just prepending to an internal List inside the ListBuffer

CodePudding user response：

Firstly I would like to address this (IMHO) totally misleading syntax

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

From the Scala Doc:

/**
* 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]

To clarify this syntax, here is an example of what this would look like with postfix notation (as you have) as compared to normal infix notation (apply a function to an object)

// 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)

What you are really writing above is this:

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

Semantically, append is what it appears to do, but with infix notation, we see the prefix is the argument to this function, not the suffix.

As to the performance of concat both list and listbuffer have the same signature:

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

Thus concat is likely implemented using the append operations of their respective types, for Lists, this is linear; For a ListBuffer, this is constant. For small lists/buffers, however, this difference is likely arbitrary.