flatten nested hash - recursive vs non-recursive

flattener.rb

require 'pry'

data = {
  a: {
    alfa: "alfa",
    beta: "beta"
  },
  b: 2,
  c: {
    alfa: {
      first: "first",
      second: "second",
      third: {
        x: "x",
        y: "y",
        z: {
          morning: "morning",
          afternoon: "afternoon",
          evening: {
            i: {
              ii: {
                iii: {
                  iv: "forth"
                }
              }
            }
          }
        }
      }
    }
  }
}

class Flattener

  def initialize(hash)
    @hash = hash
    @result = {}
    @result_iter = {}
    @paths = hash.keys.map { |key| [key] }
  end

  ######################################
  #   Recursive
  #
  def flatten(hash = @hash, old_path = [])
    hash.each do |key, value|
      current_path = old_path + [key]

      if !value.respond_to?(:keys)
        @result[current_path.join(".")] = value
      else
        flatten(value, current_path)
      end
    end

    @result
  end

  ########################################
  #  Non recursive
  #
  def flatten_iter
    until @paths.empty?
      path = @paths.shift
      value = @hash
      path.each { |step| value = value[step] }

      if value.respond_to?(:keys)
        value.keys.each { |key| @paths << path + [key] }
      else
        @result_iter[path.join(".")] = value
      end
    end

    @result_iter
  end

  def are_the_same?
    flatten == flatten_iter
  end

end

flattener = Flattener.new(data)

require 'pp'

pp flattener.flatten

pp flattener.flatten_iter

pp flattener.are_the_same?

require "benchmark"

Benchmark.bm do |x|
  x.report(:recursive)  {  100_000.times { flattener.flatten } }
  x.report(:iterative)  {  100_000.times { flattener.flatten_iter } }
end

Benchmark.bm do |x|
  x.report(:recursive)  {  1_000_000.times { flattener.flatten } }
  x.report(:iterative)  {  1_000_000.times { flattener.flatten_iter } }
end


# {"a.alfa"=>"alfa",
#  "a.beta"=>"beta",
#  "b"=>2,
#  "c.alfa.first"=>"first",
#  "c.alfa.second"=>"second",
#  "c.alfa.third.x"=>"x",
#  "c.alfa.third.y"=>"y",
#  "c.alfa.third.z.morning"=>"morning",
#  "c.alfa.third.z.afternoon"=>"afternoon",
#  "c.alfa.third.z.evening.i.ii.iii.iv"=>"forth"}
# {"b"=>2,
#  "a.alfa"=>"alfa",
#  "a.beta"=>"beta",
#  "c.alfa.first"=>"first",
#  "c.alfa.second"=>"second",
#  "c.alfa.third.x"=>"x",
#  "c.alfa.third.y"=>"y",
#  "c.alfa.third.z.morning"=>"morning",
#  "c.alfa.third.z.afternoon"=>"afternoon",
#  "c.alfa.third.z.evening.i.ii.iii.iv"=>"forth"}
# true
#        user     system      total        real
# recursive  4.760000   0.000000   4.760000 (  4.760669)
# iterative  0.010000   0.000000   0.010000 (  0.011262)
#        user     system      total        real
# recursive 49.080000   0.000000  49.080000 ( 49.070922)
# iterative  0.100000   0.000000   0.100000 (  0.111212)
# [Finished in 54.1s]

Notes:
In the real scenario this needed to be filtered only for some specific patterns. For this a lazy version could be used, which yields only the desired paths and values as an enumerator.

There is some shades of gray here... you have destructive @paths manipulations. So everything after run#1 is shows something other. Look, I think this is better:

require "benchmark"

Benchmark.bm do |x|
  x.report(:recursive)  {  100_000.times { Flattener.new(data).flatten } }
  x.report(:iterative)  {  100_000.times { Flattener.new(data).flatten_iter } }
end

Benchmark.bm do |x|
  x.report(:recursive)  {  1_000_000.times { Flattener.new(data).flatten } }
  x.report(:iterative)  {  1_000_000.times { Flattener.new(data).flatten_iter } }
end
# >>        user     system      total        real
# >> recursive  3.810000   0.010000   3.820000 (  3.863483)
# >> iterative  4.730000   0.020000   4.750000 (  4.762254)
# >>        user     system      total        real
# >> recursive 38.830000   0.080000  38.910000 ( 39.034850)
# >> iterative 45.710000   0.160000  45.870000 ( 46.087174)

but anyway - thanks! =)