Как получить доступ к вложенным ключам в хешах

Я использую Ruby on Rails с гемом ClosureTree. У меня есть вложенный хэш:

{
  :a00=>{
    :a10=>{
      :a20=>{}, 
      :a21=>{}
    }, 
    :a11=>{
      :a22=>{
        :a30=>{}, 
        :a31=>{}
      }
    }
  }
}

Я хочу найти значение любого данного ключа и всех его «супер ключей». Например, для :a30 я хочу найти его значение {} и ключи хэшей, в которые он вложен: [:a00, :a11, :a22] .

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

def deep_find(obj, key)
  return obj[key] if obj.respond_to?(:key?) && obj.key?(key)

  if obj.is_a? Enumerable
    found = nil
    obj.find { |*a| found = deep_find(a.last, key) }

    found
  end
end

Тем не менее, я не смог найти способ найти «супер-ключи».

Всего 2 ответа


Я бы пошел с чем-то вроде этого:

def find_node_path(tree, search_key)
  return unless tree.is_a?(Hash)
  return [] if tree.key?(search_key)

  tree.each do |key, node|
    path = find_node_path(node, search_key)
    return [key, *path] if path
  end

  nil
end

path = find_node_path(tree, :a30)
#=> [:a00, :a11, :a22]

# retrieve value
value = tree.dig(*path, :a30)
#=> {}

Это делает следующее, возвращает nil если текущее tree не является хешем или если search_key не может быть найден в текущей tree структуре.

Метод перебирает все пары ключ / значение хеша, рекурсивно вызывая find_node_path . Если возвращается nil это означает, что search_key не может быть найден, таким образом, search_key к следующей итерации в цикле.

Если возвращаемое значение не равно nil это означает, что search_key находится по path в node относительно tree . В этом случае добавьте path к key текущей итерации и верните его.

Примечание: хотя это решение работает, если search_key не уникален в структуре. Он вернет только первое найденное совпадение. Поскольку это решение сначала использует глубину, оно вернет [:a1, :a2] когда tree = {a1: {a2: {a3: {}}}, b1: {a3: {}}} для search_key = :a3 .


Код

def extract(h,target_key)
  return [target_key, h[target_key]] if h.key?(target_key)
  h.each do |kk,v|
    next unless v.is_a?(Hash)
    arr = extract(v,target_key) 
    return [kk,*arr] unless arr.nil?
  end
  nil
end

пример

h = {
  :a00=>{
    :a10=>{
      :a20=>{1=>2}, 
      :a21=>{3=>4}
    }, 
    :a11=>{
      :a22=>{
        :a30=>{5=>6}, 
        :a31=>{7=>8}
      }
    }
  }
}

[:a00, :a10, :a20, :a21, :a11, :a22, :a30, :a31, 3, :a32].each do |k|
  puts ":#{k} -> #{extract(h,k) || "nil"}"
end

target_key -> extract(h, target_key)

:a00 -> [:a00, {:a10=>{:a20=>{1=>2}, :a21=>{3=>4}},
                :a11=>{:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}}]
:a10 -> [:a00, :a10, {:a20=>{1=>2}, :a21=>{3=>4}}]
:a20 -> [:a00, :a10, :a20, {1=>2}]
:a21 -> [:a00, :a10, :a21, {3=>4}]
:a11 -> [:a00, :a11, {:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}]
:a22 -> [:a00, :a11, :a22, {:a30=>{5=>6}, :a31=>{7=>8}}]
:a30 -> [:a00, :a11, :a22, :a30, {5=>6}]
:a31 -> [:a00, :a11, :a22, :a31, {7=>8}]
:3   -> [:a00, :a10, :a21, 3, 4]
:a32 -> nil

объяснение

По моему опыту, единственный полезный способ объяснить, как работает рекурсивный метод, - показать результат засоления метода с помощью операторов puts и запуска примера. Более того, чтобы сохранить четкость при проверке выходных данных, необходимо делать отступы для выходных данных, которые каждый метод вызывает сам, и «отменять» выходные данные, когда метод возвращается. Я сделал это ниже для моего метода extract . Требуется время и терпение, чтобы пройти через выполненные вычисления, но любой, кто делает это, должен получить четкое представление о том, как работает этот метод, и, возможно, также узнать кое-что о рекурсивных методах вообще. Нет необходимости, конечно, понимать код ниже, который отображает выполненные вычисления.

INDENT = 6
$col = 4-INDENT
def indent
  $col += INDENT
end
def undent
  $col -= INDENT
end
def prn
  print " "*$col
end
def divide
  puts "#<p></p>"
end

def extract(h,target_key)
  divide
  indent
  prn; puts "entering extract"
  prn; puts "h=#{h}"
  prn; puts "h.key?(#{target_key}) = #{h.key?(target_key)}"
  if h.key?(target_key)
    prn; puts "returning #{[target_key, h[target_key]]}"
    undent
    divide
    return [target_key, h[target_key]]
  end
  h.each do |kk,v|
    prn; puts "  kk=#{kk}"
    prn; puts "  v=#{v}"
    prn; puts "  v.is_a?(Hash) = #{v.is_a?(Hash)}"
    prn; puts "  skip key" unless v.is_a?(Hash)  
    next unless v.is_a?(Hash)
    prn; puts "  call extract(#{v},target_key)"
    arr = extract(v,target_key)
    prn; puts "  arr=#{arr.nil? ? "nil" : arr} returned"
    if arr
       prn; puts "  target key found"
       prn; puts "  returning [#{[kk,*arr]}]"
       undent
       divide  
       return [kk,*arr]
    end
  end
  prn; puts "returning nil"
  undent
  divide 
  nil
end

extract(h,:a30)

entering extract
h={:a00=>{:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}}
h.key?(a30) = false
  kk=a00
  v={:a10=>{:a20=>{1=>2},..., :a31=>{7=>8}}}}
  v.is_a?(Hash) = true
  call extract({:a10=>{:a20..., :a31=>{7=>8}}}},target_key)

      entering extract
      h={:a10=>{:a20=>{1=>2},...,:a31=>{7=>8}}}}
      h.key?(a30) = false
        kk=a10
        v={:a20=>{1=>2}, :a21=>{3=>4}}
        v.is_a?(Hash) = true
        call extract({:a20=>{1=>2}, :a21=>{3=>4}},target_key)

            entering extract
            h={:a20=>{1=>2}, :a21=>{3=>4}}
            h.key?(a30) = false
              kk=a20
              v={1=>2}
              v.is_a?(Hash) = true
              call extract({1=>2},target_key)

                  entering extract
                  h={1=>2}
                  h.key?(a30) = false
                    kk=1
                    v=2
                    v.is_a?(Hash) = false
                    skip key
                  returning nil

              arr=nil returned
              kk=a21
              v={3=>4}
              v.is_a?(Hash) = true
              call extract({3=>4},target_key)

                  entering extract
                  h={3=>4}
                  h.key?(a30) = false
                    kk=3
                    v=4
                    v.is_a?(Hash) = false
                    skip key
                  returning nil

              arr=nil returned
            returning nil

        arr=nil returned
        kk=a11
        v={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
        v.is_a?(Hash) = true
        call extract({:a22=>{:a30..., :a31=>{7=>8}}},target_key)

            entering extract
            h={:a22=>{:a30=>{5=>6}, :a31=>{7=>8}}}
            h.key?(a30) = false
              kk=a22
              v={:a30=>{5=>6}, :a31=>{7=>8}}
              v.is_a?(Hash) = true
              call extract({:a30=>{5=>6},
                :a31=>{7=>8}},target_key)

                  entering extract
                  h={:a30=>{5=>6}, :a31=>{7=>8}}
                  h.key?(a30) = true
                  returning [:a30, {5=>6}]

              arr=[:a30, {5=>6}] returned
              target key found
              returning [[:a22, :a30, {5=>6}]]

        arr=[:a22, :a30, {5=>6}] returned
        target key found
        returning [[:a11, :a22, :a30, {5=>6}]]

  arr=[:a11, :a22, :a30, {5=>6}] returned
  target key found
  returning [[:a00, :a11, :a22, :a30, {5=>6}]]

  #=> [:a00, :a11, :a22, :a30, {5=>6}]

Есть идеи?

10000