Ruby 按父子关系对哈希数组排序

Question

所以我们有散列数组

array = [
  {id: 1, parent_id: 0},
  {id: 2, parent_id: 1},
  {id: 3, parent_id: 0},
  {id: 4, parent_id: 2}
]
target_array = []

将数组 map/sort 生成以下结果的最有效 ruby 方法是什么：

target_array = [
  {id:1,children:
    [{id: 2, children: [
      {id:4, children:[]}]}]},
  {id: 3, children:[]}  
]

p.s.The 我最擅长的是为每个项目迭代整个事物，并从已经映射到 target_array.

的数组哈希中排除

Answer 1

你可以用递归来解决这个问题：

@array = [
  {id: 1, parent_id: 0},
  {id: 2, parent_id: 1},
  {id: 3, parent_id: 0},
  {id: 4, parent_id: 2}
]


def build_hierarchy target_array, n
    @array.select { |h| h[:parent_id] == n }.each do |h|
      target_array << {id: h[:id], children: build_hierarchy([], h[:id])}
    end
    target_array
end


build_hierarchy [], 0

输出：

=> [{"id"=>1, "children"=>[{"id"=>2, "children"=>[{"id"=>4, "children"=>[]}]}]}, {"id"=>3, "children"=>[]}]

此rubyfiddlehttp://rubyfiddle.com/riddles/9b643

中的实例

Answer 2

这是我尝试使用 Hash

的方法

array = [
  {id: 1, parent_id: 0},
  {id: 2, parent_id: 1},
  {id: 3, parent_id: 0},
  {id: 4, parent_id: 2}
]

  target_hash = Hash.new { |h,k| h[k] = { id: nil, children: [ ] } }

  array.each do |n|
      id, parent_id = n.values_at(:id, :parent_id)
      target_hash[id][:id] = n[:id]
      target_hash[parent_id][:children].push(target_hash[id])  
  end
 puts target_hash[0]

输出：

{:id=>nil, :children=>[{:id=>1, :children=>[{:id=>2, :children=>[{:id=>4, :children=>[]}]}]}, {:id=>3, :children=>[]}]}

Answer 3

我认为最好的一个最多有O(nlog(n))的时间复杂度。我给出了我的非哈希值：

array = [
  {id: 1, parent_id: 0},
  {id: 2, parent_id: 1},
  {id: 3, parent_id: 0},
  {id: 4, parent_id: 2}
]

# This takes O(nlog(n)).
array.sort! do |a, b|
    k = (b[:parent_id] <=> b[:parent_id])
    k == 0 ? b[:id] <=> a[:id] : k
end

# This takes O(n)
target_array = array.map do |node|
    { id: node[:id], children: [] }
end

# This takes O(nlog(n))
target_array.each_with_index do |node, index|
    parent = target_array[index + 1...target_array.size].bsearch do |target_node|
        target_node[:id] == array[index][:parent_id]
    end
    if parent
        parent[:children] << node
        target_array[index] = nil
    end
end

# O(n)
target_array.reverse.compact
# =>
# [{:id => 1, :children =>[{:id=>2,:children=> [ {:id=>4, 
# :children=>[]}]}]},
# {:id=>3, :children=>[]} ]

所以我一般使用 O(nlog(n))。

顺便说一下，当我简单地测试现有的解决方案时，我发现 Gagan Gami 的效率最高（略高于我的），我相信它也是 O(nlog(n))，虽然不是很明显。但是目前接受的解决方案需要 O(n^2) 时间。

Answer 4

我会使用递归，但以下可以很容易地转换为 non-recursive 方法。

首先构造一个散列，将 parent 链接到它们的 children (p2c)。为此，使用 Hash#update（又名 merge!）的形式，它使用一个块来确定要合并的两个哈希中存在的键的值：

@p2c = array.each_with_object({}) { |g,h|
  h.update(g[:parent_id]=>[g[:id]]) { |_,ov,nv| ov+nv } }
  #=> {0=>[1, 3], 1=>[2], 2=>[4]}

还有许多其他方法可以构造此哈希。这是另一个：

@p2c = Hash[array.group_by { |h| h[:parent_id] }
                 .map { |k,v| [k, v.map { |g| g[:id] }] }]

现在构造一个递归方法，其唯一参数是 parent:

def family_tree(p=0)
  return [{ id: p, children: [] }] unless @p2c.key?(p)
  @p2c[p].each_with_object([]) { |c,a|
    a << { id:c, children: family_tree(c) } }
end

我们得到：

family_tree
  #=> [ { :id=>1, :children=>
  #               [
  #                { :id=>2, :children=>
  #                          [
  #                            { :id=>4, :children=>[] }
  #                          ]
  #                }
  #              ]
  #    },
  #    { :id=>3, :children=>[] }
  #  ]

最初构造散列 @p2c 应该会非常有效。

Ruby 按父子关系对哈希数组排序

Ruby sort array of hashes by child-parent relation

ruby

iteration