Elegance Can Be the Enemy of Efficiency

I’ve been auditing some of the advanced Scala courses offered by École Polytechnique Fédérale de Lausanne, and as always am curious about my own solutions compared against what other people come up with.

One of the things I love about Scala is its elegance. Once you understand the language, you can achieve some really complex things quickly and easily — and, elegantly. So, a problem posed in the coursework is to write a function that, given a character in a game field, returns the first index of that character in the field.

After writing my own solution, I Googled a few other solutions. Here’s one:

def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = {
   val ys = levelVector map (_ indexOf c)
   val x = ys indexWhere (_ >= 0)
   Pos(x, ys(x))
}

This is pretty elegant. In fact, I was first taken by how functional it looked — more functional than my own code. But there’s a problem. This elegant code is potentially very inefficient.

Let’s assume the game field is big. It consists of a Vector of Vectors, and the above code searches the entire game field. That is, even if the character matches the very first element in the field, all the rest of the elements will be scanned:

  1. ys maps over the entire Vector of Vector scanning for the index of c.
  2. x then scans the vector ys for a positive hit.
  3. Then the coordinate is returned from the points described by x and ys(x).

So the obvious problem here is our elegant, functional, good looking code could be terribly inefficient. Here’s my implementation:

def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = { 
   @tailrec def iterate(x: Int): Pos = levelVector(x).indexOf(c) match { 
      case y if y > -1 => Pos(x, y) 
      case _ => iterate(x + 1) 
   } 
   iterate(0) 
}

Ok, it’s not as pretty, it’s longer, but — it’s still functional by design. More important, it will look for the character using a linear search, and stops when it finds the character. It’s efficient:

  1. We start in the first Vector, checking for the index of the character.
  2. As soon as we find it, the function returns. Otherwise, it recurses and moves to the next Vector.

It’s not as pretty but it preserves efficient design. Just because we can write pretty, elegant code doesn’t mean we always should.

Incidentally, you could also achieve nearly the same efficiency using something like this:

val row = levelVector.indexWhere(_.contains(c))
val col = levelVector(row).indexOf(c)

Personally, I prefer to avoid any potential inefficiency — but, over-optimizing can also be a problem. It’s probably best to find a happy balance. Don’t ignore efficiency, but don’t spend all your time optimizing situations that, quite likely, don’t really need the effort.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s