4

How do I get a subset of a map?

Assume we have

val m: Map[Int, String] = ...
val k: List[Int]

Where all keys in k exist in m.

Now I would like to get a subsect of the Map m with only the pairs which key is in the list k.

Something like m.intersect(k), but intersect is not defined on a map.

One way is to use filterKeys: m.filterKeys(k.contains). But this might be a bit slow, because for each key in the original map a search in the list has to be done.

Another way I could think of is k.map(l => (l, m(l)).toMap. Here wie just iterate through the keys we are really interested in and do not make a search.

Is there a better (built-in) way ?

John Threepwood
  • 15,593
  • 27
  • 93
  • 149
  • Couldn't you just iterate over the keys in the list and build a new map from it? Also when you say "might be slow" have you tried it and determined that it is too slow for your use case? – Emil L Aug 27 '12 at 18:13

3 Answers3

16
m filterKeys k.toSet

because a Set is a Function.

On performance: filterKeys itself is O(1), since it works by producing a new map with overridden foreach, iterator, contains and get methods. The overhead comes when elements are accessed. It means that the new map uses no extra memory, but also that memory for the old map cannot be freed.

If you need to free up the memory and have fastest possible access, a fast way would be to fold the elements of k into a new Map without producing an intermediate List[(Int,String)]: 

k.foldLeft(Map[Int,String]()){ (acc, x) => acc + (x -> m(x)) }
Luigi Plinge
  • 50,650
  • 20
  • 113
  • 180
2

val s = Map(k.map(x => (x, m(x))): _*)

Sergey Weiss
  • 5,944
  • 8
  • 31
  • 40
  • Is that was allowed? Good etiquette? – Pablo Lalloni Aug 31 '12 at 15:21
  • 1
    @PabloLalloni Sure, collaborative answers and questions are commonplace at SO. And your proposal is a good one – Sergey Weiss Aug 31 '12 at 15:27
  • 1
    `k.view.map(x => x -> m(x)).toMap` would be slightly more efficient since you don't produce the intermediate List. Alternatively `val s: Map[Int, String] = k.map(x => x -> m(x))(collection.breakOut)` will do the mapping directly into a `Map`. – Luigi Plinge Sep 01 '12 at 19:07
1

I think this is most readable and good performer:

k zip (k map m) toMap

Or, method invocation style would be:

k.zip(k.map(m)).toMap

Pablo Lalloni
  • 2,615
  • 19
  • 20