CODEWITHSUNDEEP
scalascala-collections
Yair Halberstadt
Yair Halberstadt

Reputation: 6831

Don't return same type from filter for efficiency

Let's say I have a Map in scala.

Map.filter returns a Map. That means that it has to create a Map containing all the remaining items after the filter.

Since creating a map is not cheap in general (approximately O(nlog(n))), this is wasteful if all I want to do is iterate over the filtered results.

For example:

val map = Map(1 -> "hello", 50 -> "world", 100 -> "hi", 1000 -> "bye")
val filtered = map.filter(x => x._1 < 100)
for(x <- filtered) println(x._2)

I don't think using map.toIterable helps since the underlying is still a Map, and filter is virtual.

I don't know whether map.view has the required behavior or not.

I think map.iterator would work, but that means I can't iterate over the iterator twice. I suppose I could use map.iterator.filter(x => x._1 < 100).toList?

I could do map.map(x => (x)), but that means iterating over the Map twice.

What's the simplest, most idiomatic, not unnecessarily inefficient way of doing what I want?

Upvotes: 0

Views: 57

Answers (2)

Levi Ramsey
Levi Ramsey

Reputation: 20551

Note that if all you want to do is iterate in a for-comprehension or similar (i.e. flatMap, foreach, map), an intermediate collection isn't created:

for (x <- map if (x._1 < 100)) println(x._2)  // Doesn't create an intermediate Map

This desugars to

map.withFilter(x => x._1 < 100).foreach(x => println(x))

and withFilter is non-strict.

Upvotes: 1

C4stor
C4stor

Reputation: 8026

Use collect.

val map = Map(1 -> "hello", 50 -> "world", 100 -> "hi", 1000 -> "bye")
val filtered : Iterable[String] = map.collect{
 case(x,y) if x<100 => y
}

Gives you only the values for which the key satisfies the condition

Upvotes: 1

Related Questions