Каков наиболее эффективный способ сбора массивов вложенных хеш-ключей, которые обращаются к конечным узлам? - PullRequest
Новая
       19

Каков наиболее эффективный способ сбора массивов вложенных хеш-ключей, которые обращаются к конечным узлам?

1 голос
/ 13 марта 2012

У меня есть вложенный хэш, и мне нужен один массив, где каждый элемент представляет собой массив ключей, представляющий путь через вложенный хэш к не-хэшам (листовые узлы).

Например, с учетом ввода: 

x = Hash.new
x["a"] = Hash.new
x["a"]["b"] = Hash.new
x["a"]["b"]["c"] = "one"
x["a"]["b"]["d"] = "two"
x["a"]["e"] = "three"
x["f"] = Hash.new
x["f"]["g"] = "four"

Я хотел бы вывод: 

[["a", "b", "c"], ["a", "b", "d"], ["a", "e"], ["f", "g"]]

Приведенный ниже код работает с использованием двух рекурсивных методов: один для генерации вложенного массива, а другой для его удаления!.

Моя интуиция Ruby говорит мне, что должен быть гораздо более эффективный и элегантный способ достижения этого. Кто-нибудь может предложить решение для игры в гольф или решение Ruby Way? 

def collect_key_paths(object, path=[])
  result = nil
  if object.is_a?(Hash)
    path_for_current_hash = object.map do |key, value|
      incremented_path = [path, key].flatten
      collect_key_paths(value, incremented_path)
    end
    result = path_for_current_hash
  else
    result = path
  end
  result
end

def smoothe(array, store=[])
  if array.none? { |element| element.is_a?(Array) }
    store << array
  else
    array.each do |element|
      store = smoothe(element, store)
    end
  end
  store
end


x = Hash.new
x["a"] = Hash.new
x["a"]["b"] = Hash.new
x["a"]["b"]["c"] = "one"
x["a"]["b"]["d"] = "two"
x["a"]["e"] = "three"
x["f"] = Hash.new
x["f"]["g"] = "four"

nested_key_paths = collect_key_paths(x)
puts "RESULT:#{smoothe(nested_key_paths)}"

Результат этого кода, работающего в версии 1.9.2: 

RESULT:[["a", "b", "c"], ["a", "b", "d"], ["a", "e"], ["f", "g"]]

Спасибо!

Ответы [ 3 ]

0 голосов
/ 13 марта 2012 
class Hash
  def collect_key_paths(path=[])
    self.each.with_object([]) do |(k, v), a|
      if v.kind_of?(Hash)
        a.push(*v.collect_key_paths(path + [k]))
      else
        a << path + [k]
      end
    end
  end
end

Итак, следуя вашему примеру: 

x = Hash.new
x["a"] = Hash.new
x["a"]["b"] = Hash.new
x["a"]["b"]["c"] = "one"
x["a"]["b"]["d"] = "two"
x["a"]["e"] = "three"
x["f"] = Hash.new
x["f"]["g"] = "four"

puts x.collect_key_paths.inspect
0 голосов
/ 13 марта 2012

Небольшая вариация: 

def collect_key_paths(hash)
  paths = []
  hash.each do |k, v|
    paths.concat( 
      Hash === v ? 
        collect_key_paths(v).map{ |path| [k, *path]} : 
        [k] 
    )
  end
  paths
end
0 голосов
/ 13 марта 2012

Я не уверен, что это «лучший» способ, но вы можете избежать необходимости повторять его дважды, чтобы «сгладить» результат: 

def collect_key_paths(hash, path = [])
  items = []
  hash.each do |k, v|
    if v.is_a?(Hash) 
      items.push(*collect_key_paths(v, path + [k]))
    else
      items << (path + [k])
    end
  end
  items
end

p collect_key_paths(x)
...