list - Erlang 多対多リストの再構築

Question

多対多の関係を解析する必要があります。

次のようなリストがあります：

[
 {item1, [rel1, rel2, rel3]},
 {item2, [rel2, rel5]},
 {item3, [rel1, rel4]}, 
 ...
]

I need to build new list like:
[
 {rel1, [item1, item3]},
 {rel2, [item1, item2]},
 ...
]

どうすれば効率的にできますか？

Answer 1

dict を使用した最も効率的な方法:

F = fun({Item,Rels}, Dict) ->
  H = fun(L) -> [Item|L] end,
  G = fun(Rel, D) -> dict:update(Rel, H, [Item], D) end,
  lists:foldl(G, Dict, Rels)
end,
dict:to_list(lists:foldl(F, dict:new(), Input)).

ets を使用すると、GC の負荷が少ないため、本当に大きなデータの場合は高速になる可能性があります。

Tab = ets:new(ok, [private]),
[ ets:insert(Tab,
  {Rel, case ets:lookup(Tab, Rel) of
      [] -> [Item];
      [{_, L}] -> [Item|L]
    end})
  || {Item, Rels} <- Input, Rel <- Rels ],
Result = ets:tab2list(Tab),
ets:delete(Tab),
Result.

編集：R17以降はマップがあり、R18以降は大量のキーでも効率的であるため、マップを使用したより効率的なバージョンがあります：

F = fun({Item, Rels}, Map) ->
  G = fun(Rel, M) -> maps:put(Rel, [Item|maps:get(Rel, M, [])], M) end,
  lists:foldl(G, Map, Rels)
end,
maps:to_list(lists:foldl(F, #{}, L)).

Answer 2

convert_relation(Relations) ->  
    Dict = 
        lists:foldl(fun({Item, RelList}, Dict1) ->
                            lists:foldl(fun(Rel, Dict2) ->
                                                dict:append(Rel, Item, Dict2)
                                        end, Dict1, RelList)
                    end, dict:new(), Relations),
    dict:to_list(Dict).