Investigating Recursive vs Iterative performance in Map traversal
NODES = 0..1 | |
LENGTH = 2 | |
INFINITY = 1.0/0 | |
class PriorityQueue < Hash | |
def pop! | |
smallest_pair = self.min{ |a,b| a[1] <=> b[1]} | |
self.delete(smallest_pair[0]) if smallest_pair | |
smallest_pair | |
end | |
end | |
class Path < Array | |
def distance | |
(any?)? inject(0) { | sum, edge | sum += edge[LENGTH] } : INFINITY | |
end | |
end | |
class RecursiveApproach | |
def RecursiveApproach.unused_paths(start_node, end_node, graph) | |
graph - self.shortest_path(start_node, end_node, graph) | |
end | |
def RecursiveApproach.shortest_path(start_node, end_node, graph) | |
adjacent_edges = graph.select{ | edge | edge[NODES].include?(start_node) } | |
remaining_edges = graph - adjacent_edges | |
shortest_path = Path.new | |
adjacent_edges.each do | edge | | |
path = Path.new [edge] | |
neighbor_node = (edge[NODES] - [start_node])[0] # ['A', 'B'] - ['A'] => ['B'] | |
unless neighbor_node == end_node | |
path_ahead = shortest_path(neighbor_node, end_node, remaining_edges) | |
(path_ahead.empty?)? path.clear : path.concat(path_ahead) | |
end | |
shortest_path = path if path.distance < shortest_path.distance | |
end | |
shortest_path | |
end | |
end | |
class IterativeApproach | |
def IterativeApproach.unused_paths(start_node, end_node, graph) | |
graph - self.shortest_path(start_node, end_node, graph) | |
end | |
def IterativeApproach.shortest_path(start_node, end_node, graph) | |
@previous = {} | |
@final_distances = {} | |
queue = PriorityQueue.new | |
queue[start_node] = 0 | |
while !queue.empty? do | |
vertex, distance = *queue.pop! | |
@final_distances[vertex] = distance | |
adjacent_edges = graph.select{ | edge | edge[NODES].include?(vertex) } | |
adjacent_edges.each do | edge | | |
neighbor_node = (edge[NODES] - [vertex])[0] | |
next if @final_distances.has_key? neighbor_node | |
distance_to_neighbor = @final_distances[vertex] + edge[LENGTH] | |
if (queue[neighbor_node].nil? or distance_to_neighbor < queue[neighbor_node]) then | |
queue[neighbor_node] = distance_to_neighbor | |
@previous[neighbor_node] = edge | |
break if neighbor_node == end_node | |
end | |
end | |
end | |
shortest_path = [] | |
current_vertex = end_node | |
while @previous[current_vertex] | |
shortest_path << @previous[current_vertex] | |
current_vertex = (@previous[current_vertex][NODES] - [current_vertex])[0] | |
end | |
shortest_path | |
end | |
end | |
require 'rubygems' | |
require 'ruby-prof' | |
require 'benchmark' | |
class Profiler | |
@rpcfn_graph = [ | |
['A', 'B', 50], ['A', 'D', 150], ['B', 'C', 250], ['B', 'E', 250], ['C', 'E', 350], | |
['C', 'D', 50], ['C', 'F', 100], ['D', 'F', 400], ['E', 'G', 200], ['F', 'G', 100] | |
] | |
@simple_graph = [ | |
['A','B', 10], | |
['A','B', 20] | |
] | |
@large_graph = [ | |
['A', 'B', 1], ['A', 'C', 10], ['A', 'D', 50], ['A', 'E', 1000], ['A', 'F', 100], | |
['B', 'C', 100], ['B', 'D', 150], ['B', 'E', 70], ['B', 'F', 500], | |
['C', 'D', 130], ['C', 'E', 70], ['C', 'D', 300], ['C', 'E', 50], ['C', 'F', 100],['C', 'G', 1000], | |
['D', 'E', 100], ['D', 'F', 120], ['D', 'G', 20], | |
['E', 'F', 20], ['E', 'G', 100], | |
['F', 'G', 80], | |
] | |
def profile(graph) | |
#Profile the Iterative approach | |
result = RubyProf.profile do | |
1000.times {IterativeApproach.unused_paths('A', 'G', graph)} | |
end | |
printer = RubyProf::GraphPrinter.new(result) | |
printer.print(STDOUT, 0) | |
#Profile the Recursive approach | |
result = RubyProf.profile do | |
1000.times {RecursiveApproach.unused_paths('A', 'G', graph)} | |
end | |
printer = RubyProf::GraphPrinter.new(result) | |
printer.print(STDOUT, 0) | |
end | |
def benchmark(graph) | |
benchmark = Benchmark.realtime do | |
10000.times {IterativeApproach.unused_paths('A', 'G', graph)} | |
end | |
puts "Iterative Approach took " + sprintf("%.5f", benchmark) + "second(s)." | |
benchmark = Benchmark.realtime do | |
10000.times {RecursiveApproach.unused_paths('A', 'G', graph)} | |
end | |
puts "Recursive Approach took " + sprintf("%.5f", benchmark) + "second(s)." | |
end | |
puts "Simple Graph:" | |
self.new.benchmark(@simple_graph) | |
puts "RPCFN Graph:" | |
self.new.benchmark(@rpcfn_graph) | |
puts "Large Graph:" | |
self.new.benchmark(@large_graph) | |
#self.new.profile(@rpcfn_graph) | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment