比较两个平等列表的惯用方法是什么？

Question

我有两个列表,我需要检查它们的元素是否相等(不是浅层检查,对于我可能依赖的元素Kernel.==/2.)

目前,我有:

[l1 -- l2] ++ [l2 -- l1] == []

它看起来有点过于复杂,对我来说并不十分惯用.我错过了什么吗？是否有更好的方法来比较两个列表的相等性？

Answer 1

我能想到的最简单的方法是对列表进行排序并进行比较:

Enum.sort(l1) == Enum.sort(l2)

这将O(n log n)及时运行,而不是基于O(n ^ 2)您的Kernel.--/2基础解决方案.

我们不能在这里使用普通的Set数据结构,因为列表可以包含重复项,并且必须跟踪它们的计数.我们可以使用Map来计算每个元素的频率,然后比较它们:

iex(1)> l1 = ~w|a a b|a
[:a, :a, :b]
iex(2)> l2 = ~w|a b|a
[:a, :b]
iex(3)> m1 = l1 |> Enum.reduce(%{}, fn x, acc -> Map.update(acc, x, 1, & &1 + 1) end)
%{a: 2, b: 1}
iex(4)> m2 = l2 |> Enum.reduce(%{}, fn x, acc -> Map.update(acc, x, 1, & &1 + 1) end)
%{a: 1, b: 1}
iex(5)> m1 == m2
false
iex(6)> l2 = ~w|a b a|a
[:a, :b, :a]
iex(7)> m2 = l2 |> Enum.reduce(%{}, fn x, acc -> Map.update(acc, x, 1, & &1 + 1) end)
%{a: 2, b: 1}
iex(8)> m1 == m2
true

这也是O(n log n)因为您可能希望使用您必须查看哪种数据表现更好的数据来对这两种解决方案进行基准测试.