CODEWITHSUNDEEP
listerlangelixir
Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 121000

What is the idiomatic way to compare two lists for equality?

I have two lists I need to check whether their elements are equal (not shallow check, for elements I might rely on Kernel.==/2.)

Currently, I have:

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

It looks a bit overcomplicated and not quite idiomatic to me. Am I missing something? Is there a better way to compare two lists for equality?

Upvotes: 12

Views: 10765

Answers (2)

zxq9
zxq9

Reputation: 13154

Dogbert's solution is apt, but it is still in Orcish.

In Erlang this would be:

lists:sort(List1) == lists:sort(List2)

A deep comparison looks very nearly the same, but of course must traverse the structures within each list.

One factor to consider is that very often the ordering of a list is its meaning. Strings are a good example, so are player ranks, start positions, game hotkey locations, and last-used-longest-kept cache lists. So do keep in mind the meaning of the comparison: "Do these two lists contain the same number and type of things?" is not the same as "Are these two lists semantically identical?"

Consider comparing anagrams:

lists:sort("AT ERR GET VICE") == lists:sort("IT ERR ETC GAVE")

That works fine as an anagram comparison, but not at all as a semantic one.

Upvotes: 2

Dogbert
Dogbert

Reputation: 222118

The shortest way I can think of is to sort the lists and compare them:

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

This will run in O(n log n) time instead of O(n ^ 2) for your Kernel.--/2 based solution.

We can't use a plain Set data structure here since the list can contain duplicates and their counts must be kept track of. We can use a Map which counts the frequency of each element and then to compare them:

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

This is also O(n log n) so you may want to benchmark the two solutions with the kind of data you'll have to see which performs better.

Upvotes: 22

Related Questions