CODEWITHSUNDEEP
scalacomplexity-theory
KyBe
KyBe

Reputation: 842

What is the complexity of converting scala collection from one type to another?

I would like to know the complexity of converting scala collection operations like following ones :

List.fill(n)(1).toArray
Array.fill(n)(1).toList
ArrayBuffer( Array.fill(n)(1):_* )

I suppose that for those exemples we need to loop over all elements so it will be O(n), unfortunately i don't know the subroutines under those conversions so the complexity may be optimized.

Don't hesitate to add complexity for others kind of scala conversions.

Upvotes: 0

Views: 274

Answers (1)

Gabriele Petronella
Gabriele Petronella

Reputation: 108091

I took a quick look at the source code, and they all appear to be O(n) as you thought.

Here's for example the subroutine copyToArray (used by toArray):

override /*TraversableLike*/ def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
  var i = start
  val end = (start + len) min xs.length
  val it = iterator
  while (i < end && it.hasNext) {
    xs(i) = it.next()
    i += 1
  }
}

source

As you can see it simply iterates over the collection linearly.

Upvotes: 3

Related Questions