elixir - 使用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_id 在列表中的位置要早于较低的 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

核心思想是，我们保留一个由 Foo 的 parent_id 键控的临时映射，每当我们看到当前 Foo 的 id存在于 map 中，我们将其 children 取出并将其放入当前 Foo 中，然后将当前 Foo 插入 其 parent_id 的 >children。最后，我们取出唯一具有 parent_id: nil 的 Foo，并使用它。

演示:

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