Concat两个列表和Maps在长生不老药中更有效

Question

我有2个地图列表：

list1 = 
[
 %{amount: 1, id: 112006},
 %{amount: 1, id: 78798},
 %{amount: 6, id: 92572},
 %{amount: 1, id: 89750},
 %{amount: 1, id: 81418},
 %{amount: 3, id: 92062},
 %{amount: 1, id: 82373},
 %{amount: 1, id: 92856}...
]

和

list2 =
[
 %{count: 5, id: [112006, 92062, 92856, 67812, 70736], name: "Object 1"},
 %{count: 655, id: [92572, 22432, 32368, 34180, 34181, 34182, ...],    name: "Object 2"},
 %{count: 238, id: [26052, 30430, 37067, 37068, 41228, 42686, ...], name: "Object 3"}
 ...
]

List1在IT和List2中带有30000 地图，带有大约100张地图，ID在两个列表中都是相同的，我想将两个列表集中到一个列表中：

[
 %{count: 5, all_count: 5 name: "Object 1"},
 %{count: 655, all_count: 3, name: "Object 2"},
 ....
]

使用新的all_count-key，它是List1中所有数量的总和，列表2中的ID阵列中的同一ID。

我做到了：

Enum.map(list2, fn(map) ->
    all_count =
      list1
      |> Enum.filter(&Enum.member?(map.id, &1.id))
      |> Enum.map(&(&1.amount))
      |> Enum.sum
     Map.put(map, :all_count, all_count)
   end)

巫婆工作非常慢，我需要更快的东西，尝试流动：

Enum.map(list2, fn(map) ->
    all_count =
      list1
      |> Flow.from_enumerable()
      |> Flow.filter(&Enum.member?(map.id, &1.id))
      |> Flow.map(&(&1.amount))
      |> Enum.sum
     Map.put(map, :all_count, all_count)
   end)

速度更快，但没有太多的技巧如何更快地获取它？tia。

Answer 1

问题的主要键是过滤器是O(n)操作，因此在每次迭代中，您都在列表的所有30k元素上循环。

这使您的整个操作O(n^2)复杂性，因此不可缩放。

通过将第一个列表转换为hash_table，可以将您的问题减少到O(n)的复杂性：

list1 = [
 %{amount: 1, id: 112006},
 %{amount: 1, id: 78798},
 %{amount: 6, id: 92572},
 %{amount: 1, id: 89750},
 %{amount: 1, id: 81418},
 %{amount: 3, id: 92062},
 %{amount: 1, id: 82373},
 %{amount: 1, id: 92856}
]
hash_table = Enum.reduce(list1, %{}, fn e, a -> Map.merge(a, %{e.id => e}) end)

评论中建议的更好的Map.merge替代方法是：

hash_table = Enum.reduce(list1, %{}, &Map.put(&2, &1.id, &1))

因此，您将留下以下内容：

%{
  78798 => %{amount: 1, id: 78798},
  81418 => %{amount: 1, id: 81418},
  82373 => %{amount: 1, id: 82373},
  89750 => %{amount: 1, id: 89750},
  92062 => %{amount: 3, id: 92062},
  92572 => %{amount: 6, id: 92572},
  92856 => %{amount: 1, id: 92856},
  112006 => %{amount: 1, id: 112006}
}

现在，您可以使用O(1(访问>使用O(log n(访问的o(1(访问的元素，而不是在每个元素上循环循环，例如。list1[82373]将为您提供%{amount: 1, id: 82373}，您可以从中获得金额。如果您不预见到除了金额以外的任何这些数据点中都需要进一步的键，则可以通过将id点指向数量值来进一步促进事情。

拥有概念验证后，您可以修改程序以完全采用Hash_map数据结构，以免经常将list1转换为hash_map结构。也许您还可以考虑将其全部放在路上的ETS表中，这可能会给您O(1)查找访问，如文档中所述：

这些提供了将大量数据存储在 Erlang运行时系统，并有持续的访问数据。

Answer 2

您可以尝试什么，而不是过滤list1中每个映射功能中的ID是将其转换为映射，其中键是id，并且值是amount Parts：

map1 = list1 |> List.foldl(%{}, fn(m, acc) -> Map.put(acc, m.id, m.amount) end)
# Result
%{
  78798 => 1,
  81418 => 1,
  82373 => 1,
  89750 => 1,
  92062 => 3,
  92572 => 6,
  92856 => 1,
  112006 => 1
  ...
}

然后您可以稍微调整代码。或者，您可以使用list.foldl/3尝试构建结果列表：

List.foldl(list2, [], fn(map, acc) ->
  map_count = Map.take(map, [:count, :name])
  count = map.id |> List.foldl(0, &(map1[&1] + &2))
  acc ++ [Map.put(map_count, :all_count, count)]
end)