树转数组算法（Ruby）

Question

我有一个分支模型，由parent_id和child_id组成。我想获取一个父/子关系数组，而不是查询每个父级的孩子。

对于这个表：

Parent_id | Child_id
1         | 2
1         | 6
1         | 9
2         | 3
3         | 10
4         | 7

我想获取1的子元素，以及他们的子元素，如下所示：

{2 => {3 => {10}}, 6, 9}

不需要查询每个父级的子级。

是否有一种高效实现此算法的方法，或者我需要遍历每个父级？谢谢。

- Gal

---

[2 => [3 => [10]], 6, 9] 不是有效的 Ruby 代码。是数组还是哈希表？ - tokland

@tokland不重要，我正在寻找哈希/数组表示。 - Gal

Answer 1

一种广度优先搜索算法就能够胜任此任务。

def build_tree(i, edges)
    list = {}
    out_nodes = edges.select {|e| e[0] == i}.map {|e| e[1]}.uniq
    out_nodes.each {|n| list[n] = build_tree(n, edges)}
    list
end

edges = [[1,2],[1,6],[1,9],[2,3],[3,10],[4,7]]
puts build_tree(1, edges)
# {2=>{3=>{10=>{}}}, 6=>{}, 9=>{}}

- ZelluX

---

弄错了时间。这个程序运行速度更快，只需要3.6秒，就可以运行10万次。基准测试 pastie。 - Zabba

Answer 2

一种功能性和递归的方法：

require 'facets'

def create_tree(pairs, root)
  relationships = pairs.map_by { |parent, child| [parent, child] }  
  get_children = proc do |parent|
    (relationships[parent] || []).mash do |child| 
      [child, get_children.call(child)]
    end
  end  
  get_children.call(root)
end

pairs = [[1, 2], [1, 6], [1, 9], [2, 3], [3, 10], [4, 7]]
p create_tree(pairs, 1)
#=> {6=>{}, 2=>{3=>{10=>{}}}, 9=>{}}

[编辑] 没有facets（现在你将会明白我使用它的原因！）：

def create_tree(pairs, root)
  relationships = Hash[pairs.group_by { |p, c| p }.map { |p, ary| [p, ary.map { |p, c| c }] }]
  get_children = proc do |parent|
    Hash[(relationships[parent] || []).map do |child| 
      [child, get_children.call(child)]
    end]
  end  
  get_children.call(root)
end

- tokland

---

Facets对我不起作用（我得到了500错误）。你知道为什么吗？ - Gal

你尝试过执行 gem install facets 命令吗？ - Zabba

我在我的Gemfile文件中有它（我正在使用Rails），运行了bundle。 - Gal

弄错了时间。第一段代码是5秒，运行10万次。 - Zabba

@zabba，感谢您的基准测试。那么这段代码比命令式的代码更快吗？这有点令人惊讶，也许ZelluX的代码不是最快的实现。 - tokland

第二段代码稍微快一些，只需要4.5秒。与您的第一段和第二段代码相比，ZelluZ的速度快了约1到1.5秒。 - Zabba