CODEWITHSUNDEEP
performancescala
shakedzy
shakedzy

Reputation: 2893

Scala: mutable collections indexing is faster than immutable?

I'm currently looking for a collection type in Scala that will be the fastest to query by index - meaning, if x is my collection, I want it to have the fastest possible performance for searching x(i) for any index i. Also, x is cannot be changed in run-time.

Looking in the Scala Collections Performance Characteristics, it seems that the best performance of O(1) are given by the Java Array, mutable.ArrayBuffer and mutable.ArraySeq (as String and Range are not useful in my case). This is surprising, as I was expecting the immutable collections to be faster, as they support less functionality. The best performance by an immutable collection are given by Vector with O(~1), which, as far as I understand, are at-best as good as O(1).

Am I missing something here, or are mutable collections truly have better search performance?

Upvotes: 1

Views: 458

Answers (1)

puhlen
puhlen

Reputation: 8519

Scala has no immutable array and an array is the structure with be best possible random index access. If there was an immutable array it would have the same performance as the mutable version.

It's not about mutable vs immutable, it's about the data structures used.

Upvotes: 4

Related Questions