12/14/08

Playing with Scala 5: improving code, use of views and comprehensions

After reading about different optimization to pathfinding algorithms, I decided to improve my Dijkstra implementation by using a priority queue instead of a set for the unvisited nodes. Using the “weight” of the vertex as the priority, we can avoid searching the whole set for the minimum and we reduce the cost of the operation from O(n) to O(log n).

The first change is replace the set with Scala's priority queue:


val unvisited=new PriorityQueue[Node]()




But as it is, it will not compile: the priority queue's signature is


class PriorityQueue[A](implicit view$1 : (A) => Ordered[A]) extends ResizableArray[A] with CloneableCollection


You need to provide an implicit conversion from the parameter type A to the type Ordered[A]. But nothing to worry about: is as easy as


implicit def node2ordered(n: Node): Ordered[Node] = new Ordered[Node] {

//reverse the comparation so highest priority = lower cost

def compare(y: Node): Int = -(n.weight.compare(y.weight))

}


Look at the improveDistance function, it does two things: filters the nodes and updates the distance if we can improve it. I think is better if we split into two different functions, separating the filtering from the updating, so instead of:


def improveDistance(a:Edge) ={
if (a.from.weight+a.weight< a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}


we get:

def canImprove(a:Edge)=(a.from.weight+a.weight< a.to.weight)

and

def improveDistance(a:Edge) ={

a.to.weight=a.from.weight+a.weight

a.to.previous=a.from

a.to

}


Then, instead of a function map over the nodeEdges, we have to filter and then map:


vertx.nodeEdges.map(improveDistance(_))


is replaced by


vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_)


that gives a better picture of the steps involved.

As we need to add the updated nodes to the priority queue so they can “float” to the top, the line would look like:


unvisited++ (vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_))


But I don't really think the explicit use of map and filter helps readability.

Enter Scala's for comprehensions: we can replace the map/filter with a comprehension:


for (v <- vertx.nodeEdges if canImprove(v)){

unvisited+improveDistance(v)

}

Nothing fantastic, but an improvement, isn't it?

For future posts, I'm planning on generalizing the algorithm into a A* pathfinding with different heuristic functions... stay tuned!

3 comments:

James Iry said...

Great series so far. I'm looking forward to A* - it's a fun one. BTW, in your view bound on Ordered you can solve the problem with an implicit conversion as you have, or you can do it with "Node extends Ordered[Node]". Either works with view bounds. The advantage of implicits is that they're flexible; you can add them later as needed. The advantage to direct extension is performance; there's no need to run the conversion routine, with the extra object creation it implies, every time you add a Node.

Unknown said...

@James
Glad you like it... I enjoy your posts too :)
I was sure that there was some way to use the queue without the implicit conversion, but after fumbling a little I couldn't do it.
My rationalization to use the implicit was: I have to reverse the order of the comparation but I don't want to always have "more weight < less weight".
Anyway I found that works if I do:
trait Weight extends Ordered[Node]{
var weight= Float.PositiveInfinity
def compare(y: Node): Int =y.weight.compare(weight)
}
and makes sense: once you have weight you can compare.
BTW, where you would define "Node extends Ordered[Node]"?

Unknown said...


Techsaga, as Software development company experts, deliver inspiring, eye-catching designs and measurable campaigns that connect with target audiences, boost online marketing and encourage business growth. We can help you meet your needs across a range of full service online marketing services. Are you looking for help with great content, SEO, PPC campaigns, a full digital marketing strategy, campaign, or something else? No matter what you need, our experts can help you.