Why is mutable map slower than immutable map?

Question
1

I’m new to Scala and found out Scala is supported in LeetCode, so I use it to practice.

Things happened, when solving the first problem, 2Sum.

Here are the codes:

object Solution {
  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    def iter(pos: Int, map: Map[Int, Int]): Array[Int] = {
      val self = nums(pos)
      val other = target - self
      if (map contains other) Array(map(other), pos)
      else iter(pos + 1, map ++ Map(self -> pos))
    }
    iter(0, Map[Int, Int]())
  }
}

And this is the mutable one.

import collection.mutable.Map

object Solution {
  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    var map = Map[Int, Int]()
    def iter(pos: Int): Array[Int] = {
      val self = nums(pos)
      val other = target - self
      if (map contains other) Array(map(other), pos)
      else {
        map = map ++ Map(self -> pos)
        iter(pos + 1)
      }
    }
    iter(0)
  }
}

The run time of the first version, the immutable one, is about 700 ms, while the mutable one takes about 4200 ms. What leads to this huge difference?

BTW, it’s really slower than other language like C++. Should I worry about it?

Thanks guys!

2

It looks like you’re not actually mutating the mutable Map. You’re using it like an immutable one.

1 Like
3

For mutable maps, you want map += (self, pos) or map(self) = pos.

Also, all of this is using generic code for primitives, which means every number has to be allocated its own object. If you really want to be as fast as, say, a C++ template version, you need to use a map that is specialized for primitives. If your keys were String, the difference from C++ would be much smaller.

1 Like
4

Oh thank you guys! This makes it run as fast as immutable one!

And indeed I forgot its a generic collection. Thank u!