Building and querying an immutable phone book

Question

I wanted to get your opinion on this immutable implementation of a Phone Book using recursion to process a stream. I am especially interested in ways to speed up the code execution.

Here is an example of expected input:

8
add 811 Mom1
add 12376213 Mom2
add 1732239 Bob
find 76213
find 910
find 811
del 811
find 811

Now, here is the code

import scala.collection.immutable.HashMap
object phoneBook extends App {
override def main(args: Array[String]): Unit = {
 import scala.io.Source.fromInputStream
 import scala.annotation.tailrec
 val verbose = false
 lazy val rawLines = fromInputStream(System.in).getLines.toStream
val nQueries = (rawLines.head).head.toInt
if(verbose) println(nQueries)
 def parseLine(s:String):(Int,Array[String]) = {
 val a = s.split(" ")
 if(verbose) println(a.mkString(","))
 a(0) match {
 case "add" => {if(verbose) println(0); (0, a)}
 case "find" =>{if(verbose) println(1); (1, a)}
 case "del" => {if(verbose) println(2); (2, a)}
 }
 }
lazy val lines = (rawLines drop 1).map(parseLine)
 @tailrec def doAction(stream:Stream[(Int,Array[String])],acc:HashMap[Int,String]=HashMap.empty[Int,String]):Unit = {
 if(stream.isEmpty) Unit
 else{
 val nextAction = stream.head
 val actionDetail = nextAction._2
 nextAction._1 match {
 case 0 => doAction(stream.tail,acc.+(actionDetail(1).toInt -> actionDetail(2)) )
 case 1 => {
 println(acc.getOrElse(actionDetail(1).toInt,f"not found"))
 doAction(stream.tail,acc)
 }
 case 2 => doAction(stream.tail,acc.-(actionDetail(1).toInt ) )
 }
 }
}
doAction(lines)
 }
}

Answer 1

Your indentation needs cleaning up.

The compiler says:

$ scalac -deprecation phoneBook.scala 
phoneBook.scala:5: warning: overriding method main in trait App is deprecated: main should not be overridden

Following the example in the documentation, inside the App, you should just put your code in the object itself, without any main function.

Translating the three verbs into a numeric code is unnecessary obfuscation. Trying to handle all three kinds of commands in the same doAction function is also cumbersome.

Converting the Iterator into a Stream is counterproductive, when you intend to process each line just once. It just makes you have to (rawLines drop 1) explicitly.

You're starting with an empty phone book (cryptically named acc). Then you want to have each command transform it and pass it along to the next command. Instead of explicit recursion in the doAction function, you would be better off using a fold.

Instead of instantiating scala.collection.immutable.HashMap, you can just use a Map and let Scala do the right thing.

import scala.io.Source.fromInputStream
object phoneBook extends App {
 def add(phoneBook: Map[Int,String], number: Int, name: String) = {
 phoneBook + (number -> name)
 }
 def del(phoneBook: Map[Int,String], number: Int) = {
 phoneBook - (number)
 }
 def find(phoneBook: Map[Int,String], number: Int) = {
 println(phoneBook.getOrElse(number, "not found"))
 phoneBook
 }
 lazy val lines = fromInputStream(System.in).getLines
 val nQueries = lines.next.toInt
 lines.take(nQueries).foldLeft(Map.empty[Int,String])((phoneBook, line) => {
 line.split(" ") match {
 case Array("add", number, name) => add(phoneBook, number.toInt, name)
 case Array("find", number) => find(phoneBook, number.toInt)
 case Array("del", number) => del(phoneBook, number.toInt)
 }
 })
}

Actually, there is no need to convert the phone numbers to integers, unless you want to ensure that they are indeed numeric. In fact, in general, phone numbers should not be treated as integers, since they may contain many digits, or may have significant leading zeroes.

• Guillaume: Hi 200_success. I like your way of thinking. This is very elegant. Thanks for the great feedback.
• Guillaume: it is also over 3X faster! Would you be kind enough to point out the biggest speed-ups ?
• 200_success: I pointed out several simplifications. Try each of them independently to see which one makes the biggest difference.