使用parent_id从平面列表创建分层数据结构

Question

我有一个这样的数据结构列表:

defmodule Foo do
  defstruct [:id, :parent_id, :children]
end

lst = [
  %Foo{id: 1, parent_id: nil, children: []},
  %Foo{id: 2, parent_id: 1, children: []},
  %Foo{id: 4, parent_id: 1, children: []},
  %Foo{id: 3, parent_id: 2, children: []},
]

列表按parent_id和排序id,因此列表中较低的parent_ids比较低的s更早id.我想将该列表转换为分层数据结构:

  %Foo{id: 1, parent_id: nil, children: [
    %Foo{id: 2, parent_id: 1, children: [
      %Foo{id: 3, parent_id: 2, children: []},
    ]},
    %Foo{id: 4, parent_id: 1, children: []}
  ]}

我对递归循环有一个天真的想法Enum.filter,但这看起来效率很低.任何想法如何有效地解决这个问题？

编辑:

我似乎有一个有效的解决方案,但它也是非常低效的:

defp build_tree(root, []), do: root
defp build_tree(root, [node | tail]) do
  build_tree(insert_node(root, node), tail)
end

defp insert_node(root = %Message{}, node) do
  if root.message_id == node.parent_id do
    new_messages = case root.messages do
                     nil ->
                       [node]
                     _ ->
                       root.messages ++ [node]
                   end

    %Message{root | messages: new_messages}
  else
    acc = case root.messages do
            nil -> []
            _ -> root.messages
          end

    %Message{root | messages: insert_node(acc, node)}
  end
end

defp insert_node(root, node) do
  Enum.map(root, fn(x) -> insert_node(x, node) end)
end

[first | rest] = sorted_messages
tree = build_tree(first, rest)

想要更好的解决方案吗？

Answer 1

由于记录按照parent_id然后排序id,这是一种相当有效的方法.它只涉及遍历列表两次:一次反向,一次减少.reduce本身会执行一些Map操作,但它们仍然只是O(log n),所以整个过程是O(n log n):

tree =
  list
  |> Enum.reverse
  |> Enum.reduce(%{}, fn foo, map ->
    foo = %{foo | children: Map.get(map, foo.id, [])}
    Map.update(map, foo.parent_id, [foo], fn foos -> [foo | foos] end)
  end)
  |> Map.get(nil)
  |> hd

其核心思想是,我们不断通过楔入式临时地图parent_id的Foo,每当我们看到,目前Foo的id出现在地图上,我们把它children拿出来,把它在当前Foo,然后插入当前Foo在children它的parent_id.最后,我们拿出唯一Foo拥有parent_id: nil并使用它的东西.

演示:

defmodule Foo do
  defstruct [:id, :parent_id, :children]
end

defmodule Main do
  def main do
    list =
      [%Foo{id: 1, parent_id: nil, children: []},
       %Foo{id: 2, parent_id: 1, children: []},
       %Foo{id: 4, parent_id: 1, children: []},
       %Foo{id: 3, parent_id: 2, children: []}]

    expected =
      %Foo{id: 1, parent_id: nil, children: [
        %Foo{id: 2, parent_id: 1, children: [
          %Foo{id: 3, parent_id: 2, children: []},
        ]},
        %Foo{id: 4, parent_id: 1, children: []}
      ]}

    tree =
      list
      |> Enum.reverse
      |> Enum.reduce(%{}, fn foo, map ->
        foo = %{foo | children: Map.get(map, foo.id, [])}
        Map.update(map, foo.parent_id, [foo], fn foos -> [foo | foos] end)
      end)
      |> Map.get(nil)
      |> hd

    IO.inspect tree
    IO.inspect tree == expected
  end
end

Main.main

输出:

%Foo{children: [%Foo{children: [%Foo{children: [], id: 3, parent_id: 2}], id: 2,
   parent_id: 1}, %Foo{children: [], id: 4, parent_id: 1}], id: 1,
 parent_id: nil}
true