Ищите более разумный способ построения дерева каталогов - PullRequest
Новая
       53

Ищите более разумный способ построения дерева каталогов

0 голосов
/ 31 января 2020

У меня большой Json объект. Объект описывает среди прочего отношение типа дерева того, как его компоненты объектов связаны между собой иерархически. Объект знает, кто его дети, но не знает (напрямую), кто его родитель. «my_ha sh» ниже иллюстрирует структуру. Каждый объект имеет идентификатор 101, 102, et c., Имя «one», «two» et c и может иметь 0, 1 или более дочерних элементов. Я пытаюсь построить «путь» к каждому объекту. Например, имя объекта «пять» должно в результате иметь путь «/ один / два / четыре» в результате кода. По сути, я пытаюсь построить своего рода структуру каталогов иерархии объектов.

Код ниже работает, но выглядит довольно долго 'i sh, не очень элегантно, не очень Ruby' я sh. Буду признателен за предложение о том, как сделать это более эффективно и элегантно. И я понял, что мой код может быть не очень надежным, ie хорошо справляется с исключениями. Любые мысли или помощь приветствуются.

Кстати, я только учусь Ruby и до сих пор программировал в основном на Perl. 

class Tree
  def initialize
    @my_hash = {
      101 => ["one", [102, 107]],
      102 => ["two", [103, 104]],
      103 => ["three", []],
      104 => ["four", [105, 106]],
      105 => ["five", []],
      106 => ["six", []],
      107 => ["seven", [108]],
      108 => ["eight", []],
    }
    @child_to_parent_node = {}
    @id_to_name = {}
    @my_path_hash = {}
    @my_hash.keys.each do |key|
      @my_path_hash[key] = ""
    end
    @parent_path_id = []
  end

  def map_child_to_parent
    @my_hash.each do |key, value|
      @id_to_name.store(key, value[0])
      node_name, children = value[0], value[1]
      children.each do |child_id|
        @child_to_parent_node.store(child_id, node_name)
      end
    end
  end

  def build_path(id)
    parent = @child_to_parent_node[id]
    parent.nil? ? return : @parent_path_id << parent
    id = @id_to_name.key(parent)
    build_path(id)
    @parent_path_id
  end

  def update_tree
    @id_to_name.keys.each do |id|
      tmp_array = self.build_path(id)
      path = ""
      if (tmp_array.nil?)
        path = "/"
      else
        tmp_array.reverse.each do
          path = path + "/" + tmp_array.pop
        end
      end
      puts "id: #{id} path: #{path}"
    end
  end
end

my_tree = Tree.new
my_tree.map_child_to_parent
my_tree.update_tree

1 Ответ

0 голосов
/ 31 января 2020

На самом деле, чтобы решить эту задачу, вы должны пройти дерево от листа до root, верно? Итак, ваше представление дерева очень неудобно для этой конкретной задачи. Если вы можете обменять некоторую память на более чистое решение, я бы создал вспомогательную структуру, которая содержит родителей для каждого узла. Допустим, 

@parents = @my_hash.each_with_object({}) do |(pid, props), acc|
  _, children = props
  children.each { |cid| acc[cid] = pid }
end

#=> {102=>101, 107=>101, 103=>102, 104=>102, 105=>104, 106=>104, 108=>107}

Теперь задача может быть решена довольно кратко с помощью пары вспомогательных функций. Например: 

def id_by_name(name)
  id, _ = @my_hash.find { |k, v| v.first == name }
  id
end

def name_by_id(id)
  @my_hash[id].first
end

def path_to(node)
  path = [node]
  id = id_by_name(node)
  path.unshift(name_by_id(id)) while id = @parents[id]
  path.join("/")
end

path_to "five" #=> "one/two/four/five"

Обратите внимание: решение по-прежнему очень неэффективно - в основном потому, что для извлечения идентификатора узла по его имени мы должны выполнить итерацию по всему начальному ha sh в худшем случае. Это цена, которую мы платим за структуру данных, которая плохо подходит для задачи.

...