CODEWITHSUNDEEP
scalaperformancevectorarraybuffer
Saurav Sahu
Saurav Sahu

Reputation: 13924

Performance : Vector vs ArrayBuffer vs Array

Scala 2.11.4 - While trying to solve this problem "Sliding Window Maximum", I wrote this code :

def slidingMaximum(A: Array[Int], B: Int): Array[Int]  = {
    var ans = Vector[Int]() 
    var vectorQ = Vector[Int]()
    
    for (i <- 0 to A.length-1) {
        if (vectorQ.isEmpty) {
            vectorQ = vectorQ :+ i   
        }else{
            while (!vectorQ.isEmpty && A(vectorQ.last) <= A(i)) 
                vectorQ = vectorQ.dropRight(1)
            
            while (!vectorQ.isEmpty && (vectorQ.head <= i-B)) 
                vectorQ = vectorQ.drop(1)
            
            vectorQ = vectorQ :+ i
        }
        if (i+1 >= B) ans = ans :+ A(vectorQ.head);
    }
    return ans.toArray;
}

Since, I am a beginner in Scala Language, I used this suggestion for using Vector as Deque. When I tried replacing Vector type with Array or ArrayBuffer, the test cases failed for poor time complexity. Why can't we have var ans = ArrayBuffer[Int]() or var ans = Array[Int]() when it is mostly involved in append operation using :+?

What makes Vector really standout?

Upvotes: 1

Views: 1297

Answers (2)

Tomer Shetah
Tomer Shetah

Reputation: 8529

You can find the following post: Vector or MutableList / ListBuffer for performance which answers your question as described in the title.

Having said that, you can implement this problem really easily in Scala. Assuming we have the following vector:

val v = Vector(1, 3, -1, -3, 5, 3, 6, 7)

The following will provide what you are looking for, with good performance:

v.sliding(3).map(_.max)

Code run at Scastie.

Upvotes: 2

Mateusz Kubuszok
Mateusz Kubuszok

Reputation: 27535

It's hard to be sure without some flame graph showing where all that time is spent but I would suspect several things:

  • you are not mutating a copy, but assigning to var a modified copy
  • immutable Vector uses structural sharing to limit the cost of a single change
  • copy of Array or ArrayBuffer requires copying a whole array - you would have much better performance if you just mutated the array in place

So I would expect the performance to be:

  • best for mutating array in place (potentially wrapped in ArrayList or other mutable vector implementation)
  • worse but still acceptable for immutable vector (because of structural sharing)
  • worst for copying whole array/ArrayBuffer on each change

Upvotes: 3

Related Questions