Get total length of all lists inside a map of tuples

Question

I am working on a Scala project and I have a Map of type Map[Long, Tuple2[Boolean, List[Int]]].

I need to assign the total number of elements in all lists within the map to a variable.

I currently have a working solution, however, I want a more efficient solution. I am sure I have heard people say that you can use something called flatMap. So essentially, I want to know if there is a solution that doesn't require a loop, where I can say add the length of all lists in the map.

My solution was as follows:

for((k, v) <- myMap) total = total + v._2.length

Answer 1

In terms of efficiency, your execution would always be O(n) in your map.

If you want to use a more declarative approach, you can use foldLeft:

val total = myMap.foldLeft(0) {
  case (total, (_, list)) => total + list.length
}

foldLeft takes a seed as it's first parameter list, which we can initialize to 0. And then we iterate through each one of the lists, summing them up and returning the intermediate result. When we reach the end of the key value pair, the last accumulated element will be returned as the result.

Answer 2

There is no way to make your code more efficient, the problem is O(N) by definition.

However, if the Map is very big you may parallelize the code. You may also use a different data type other than List that doesn't need to iterate itself to compute its length.

Finally, proposing another way of getting rid of mutability.

val total =
  myMap
    .valuesIterator
    .map(_._2.length)
    .sum