Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.