Investigating Recursive vs Iterative performance in Map traversal

gistfile1.rb

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