Now the winning submission is a very nice piece of code, it's concise, easy to read, simple, well tested, and it clearly lays out it's goals, to find a recursive solution to the problem with disregard of performance. It performed ok, I did wonder however how the recursion would impact the performance on larger problem sets.

So I took Todd's code and refactored mine to work with his data structures. I also changed up my code to match his module's interface and packaged both implementations into their own classes so that there wouldn't be clashes while trying to test them. (modules are for adding abilities to classes, not for providing whole feature sets, if you see yourself including a module into main, you're doing it wrong...)

And here it is.

I ran benchmarks on a low end computer (Pentium 2.8) against 3 graphs, one with 2 nodes and 2 edges, the RPCFN example with 7 nodes and 10 edges, and a larger, more complicated one of 7 nodes and 21 edges, all of this is in the code linked above. Here's the results over 10000 iterations:

Simple Graph:

Iterative Approach took 1.54700second(s).

Recursive Approach took 0.95300second(s).

RPCFN Graph:

Iterative Approach took 6.37500second(s).

Recursive Approach took 20.62500second(s).

Large Graph:

Iterative Approach took 10.70300second(s).

Recursive Approach took 472.96200second(s).

The numbers speak for themselves, this approach doesn't scale at all well. In fact at first I thought I'd broken some of Todd's code and created an infinite loop of some sort. It's more than likely that the recursive function could be tweaked to get better performance, but short version is that if I were ever to need to implement graph traversal in Ruby for any production system, recursion would be the last approach I'd look at.

Final word

Todd's decision to use a recursive solution in this case was totally justified, readability and simplicity were massive factors in this event. That said I believe that outside of the smaller, more contrived problem scopes, recursion brings a lot of headaches and scaling issues than the iterative approaches.

this is good post.

ReplyDeleteand you can go here

http://bantalsilikon01.blogspot.com

http://kursusinternetmarketingmurah.blogspot.com

http://bumbupecelbali.blogspot.com

tanks very much.... :)