检查两个列表是否包含相同的元素

Question

我有两个返回相同长度结果列表的函数，我试图检查这些结果是否相同。列表中的顺序可以不同。我目前正在使用以下功能：

lists_are_the_same(List1, List2) ->
    List1 -- List2 =:= [].

这个函数从一个列表中减去另一个列表，并检查结果是否为空列表。问题在于，这种方法非常缓慢，在我的情况下，列表可能相当大。

是否有更快的方法来检查两个列表是否完全由相同的元素组成？

- Sergey Ovchinnik

Answer 1

更快的方法是对每个列表进行排序，然后按照以下方式进行比较：

lists_are_the_same(List1, List2) ->
    lists:sort(List1) =:= lists:sort(List2).

根据 Steve 的评论，重要的是要知道 Erlang 中所有的值都是可排序的且有 定义好的顺序，因此它适用于所有可能的列表元素。

- Hamidreza Soleimani

---

在 Erlang 中，所有的值都是可排序的，因为类型具有定义好的完全顺序。 - Steve Vinoski

@SteveVinoski没错。我在回答中提到了你的有益评论。谢谢。 - Hamidreza Soleimani

Answer 2

如果您的所有元素都是 唯一的，则可能需要使用 ordsets 而不是 lists。 您还可以查看有关使用 A-B 操作的 文档：

lists:subtract(A,B) 的复杂度与 length(A)*length(B) 成正比，这意味着如果 A 和 B 都是长列表，则速度非常慢。（如果两个列表都很长，最好选择使用有序列表和 ordsets:subtract/2。

然后，您可以通过以下方式检查它们是否相等：

ordsets:is_subset(List1,List2) andalso ordsets:is_subset(List2,List1)

- A. Sarid

---

+1. 在我使用等长但已打乱的整数列表进行微基准测试时，这似乎比排序后再进行比较要快得多。 - Dogbert