Scala reduce Sequence of Map to a Map with max value for each key

Question

I have a Seq of Map like this:

Seq(
  Map("k1" -> 1),
  Map("k1" -> 2),
  Map("k2" -> 3),
  Map("k2" -> 4)
)

I want to reduce to a single map that has values equals to the Max of each (key,value)

Expected result:

Seq(
  Map("k1" -> 2),
  Map("k2" -> 4)
)

How can I reduce the sequence of map?

`Map("k1",1)` is not valid syntax. Do you have tuples in mind `"k1" -> 1`? — Mario Galic, May 18 '20 at 20:30
Are you sure your expected result is a sequence of maps? Maybe you want just a single map? Also, it is weird that your input is a sequence of singleton maps, maybe you would rather have a sequence of tuples? — Luis Miguel Mejía Suárez, May 18 '20 at 20:37

score 2 · Answer 1 · answered May 18 '20 at 20:36

On 2.13 you can do this:

def mergeMapsWithMax[K, V : Ordering](data: IterableOnce[Map[K, V]]): Map[K, V] =
  data
    .iterator
    .flatten
    .toList
    .groupMapReduce(_._1)(_._2)(Ordering[V].max)

Which you can use use like this:

val data = Seq(
  Map("k1" -> 1),
  Map("k1" -> 2),
  Map("k2" -> 3),
  Map("k2" -> 4)
)
// data: Seq[scala.collection.immutable.Map[String,Int]] = List(Map(k1 -> 1), Map(k1 -> 2), Map(k2 -> 3), Map(k2 -> 4))


mergeMapsWithMax(data)
// res: Map[String,Int] = Map(k1 -> 2, k2 -> 4)

Mario Galic · Answer 2 · 2020-05-18T21:11:58.593

Assuming you reconsider to using list of tuples instead of sequence of maps

val tuples = List(
  ("k1", 1),
  ("k1", 2),
  ("k2", 3),
  ("k2", 4)
)

try foldLeft like so

tuples.foldLeft(Map.empty[String, Int]) { case (acc, t @ (key, value)) =>
  acc.get(key) match {
    case Some(oldValue) => if (oldValue >= value) acc else acc + t
    case None => acc + t
  }
}
// val res0: Map[String,Int] = Map(k1 -> 2, k2 -> 4)

or using updatedWith

tuples.foldLeft(Map.empty[String, Int]) { case (acc, t @ (key, value)) =>
  acc.updatedWith(key) {
    case Some(oldValue) => Some(math.max(oldValue, value))
    case None => Some(value)
  }
}
// val res1: Map[String,Int] = Map(k1 -> 2, k2 -> 4)

This should be rather performant because we are single-passing thorough the list and Map's lookup/add has by default effectively constant time.

score 1 · Answer 3 · answered May 18 '20 at 20:30

1

Seq(Map("k1" -> 1), Map("k1" -> 2), Map("k2" -> 3), Map("k2" -> 4))
  .reduce { (m1, m2) =>
    (m1.toSeq ++ m2.toSeq).groupBy(_._1).map {
      case (k, values) => k -> values.map(_._2).max
    }
  }

Produces

Map(k2 -> 4, k1 -> 2)

<script src="https://scastie.scala-lang.org/3aqyPILyRAS1tUagYcpq7w.js"></script>

answered May 18 '20 at 20:30

Ivan Stanislavciuc

7,140
15
18

I have cannot resolve .map on values "values.map(_._2).max" – michele May 18 '20 at 20:38
This is strange. The scastie code works fine. What does compiler tell you? – Ivan Stanislavciuc May 18 '20 at 20:44

score 0 · Answer 4 · answered May 18 '20 at 21:46

0

If you're determined to use maps and not tuples, use this short (but not necessarily efficient) version:

mapSeq.flatMap(_.toList).groupBy(_._1).map(_._2.max)

Otherwise, you can use

tupleSeq.groupBy(_._1).map(_._2.max)

answered May 18 '20 at 21:46

user

7,435
3
14
44

Scala reduce Sequence of Map to a Map with max value for each key

4 Answers4