從平面列表與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 s爲列表中較早比較低的id s。我想該列表進行改造，以分層數據結構：

%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。在降低自身做一些地圖操作，但是他們仍然只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已存在於地圖中，我們將其children取出並放入當前的Foo，然後將當前的Foo插入其parent_id的children中。最後，我們拿出唯一的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