33

I have a map that I need to map to a different type, and the result needs to be a List. I have two ways (seemingly) to accomplish what I want, since calling map on a map seems to always result in a map. Assuming I have some map that looks like:

val input = Map[String, List[Int]]("rk1" -> List(1,2,3), "rk2" -> List(4,5,6))

I can either do:

val output = input.map{ case(k,v) => (k.getBytes, v) } toList

Or:

val output = input.foldRight(List[Pair[Array[Byte], List[Int]]]()){ (el, res) =>
  (el._1.getBytes, el._2) :: res
}

In the first example I convert the type, and then call toList. I assume the runtime is something like O(n*2) and the space required is n*2. In the second example, I convert the type and generate the list in one go. I assume the runtime is O(n) and the space required is n.

My question is, are these essentially identical or does the second conversion cut down on memory/time/etc? Additionally, where can I find information on storage and runtime costs of various scala conversions?

Thanks in advance.

Blake Mathman
  • 2,699
  • 1
  • 23
  • 20

2 Answers2

28

My favorite way to do this kind of things is like this:

input.map { case (k,v) => (k.getBytes, v) }(collection.breakOut): List[(Array[Byte], List[Int])]

With this syntax, you are passing to map the builder it needs to reconstruct the resulting collection. (Actually, not a builder, but a builder factory. Read more about Scala's CanBuildFroms if you are interested.) collection.breakOut can exactly be used when you want to change from one collection type to another while doing a map, flatMap, etc. — the only bad part is that you have to use the full type annotation for it to be effective (here, I used a type ascription after the expression). Then, there's no intermediary collection being built, and the list is constructed while mapping.

Jean-Philippe Pellet
  • 59,296
  • 21
  • 173
  • 234
  • 3
    +1. For those seeking to understand how `breakOut` works, see Daniel Sobral's excellent answer, http://stackoverflow.com/questions/1715681/scala-2-8-breakout/1716558#1716558 – Kipton Barros Aug 10 '11 at 03:37
26

Mapping over a view in the first example could cut down on the space requirement for a large map:

val output = input.view.map{ case(k,v) => (k.getBytes, v) } toList
Ben James
  • 121,135
  • 26
  • 193
  • 155