Performance : Vector vs ArrayBuffer vs Array

Question

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?

Here's a blog post about benchmarking Scala collections that you may find helpful. — user
– user, Commented Nov 16, 2020 at 17:32

Mateusz Kubuszok · Accepted Answer · 2020-11-16 16:35:58Z

3

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

answered Nov 16, 2020 at 16:35

Mateusz Kubuszok

27.9k4 gold badges47 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Tomer Shetah · Accepted Answer · 2020-11-16 16:51:50Z

2

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.

edited Nov 16, 2020 at 16:51

answered Nov 16, 2020 at 16:33

Tomer Shetah

8,5597 gold badges31 silver badges40 bronze badges

2 Comments

Saurav Sahu Over a year ago

Thanks. That is so short and elegant, but I won't be so sure about its runtime complexity because there is some optimisation in my code. For mine it is O(N). Could it be O(N*B) for your code where B is the length of the sliding window?

Tomer Shetah Over a year ago

@SauravSahu, you are right about the complexity. But it is worth measuring the total time, since a lot is being saved here because of the immutability.

Collectives™ on Stack Overflow

Performance : Vector vs ArrayBuffer vs Array

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related