检查两个无序列表是否相等

Question

我正在寻找一种简单（快速）的方法来确定两个无序列表是否包含相同的元素：

例如：

['one', 'two', 'three'] == ['one', 'two', 'three'] :  true
['one', 'two', 'three'] == ['one', 'three', 'two'] :  true
['one', 'two', 'three'] == ['one', 'two', 'three', 'three'] :  false
['one', 'two', 'three'] == ['one', 'two', 'three', 'four'] :  false
['one', 'two', 'three'] == ['one', 'two', 'four'] :  false
['one', 'two', 'three'] == ['one'] :  false

我希望不用地图就能做到。

Answer 1

如果元素总是像示例中那样几乎排序，那么内置的.sort()（timsort）应该很快：

>>> a = [1,1,2]
>>> b = [1,2,2]
>>> a.sort()
>>> b.sort()
>>> a == b
False

如果不想就地排序，可以使用^{}。

实际上，它可能总是比collections.Counter()快（尽管渐近O(n)的时间比O(n*log(n))的时间要好）。测量一下；如果重要的话。

Answer 2

Python有一个用于无序（散列）事物集合的内置数据类型，称为set。如果将两个列表转换为集合，则比较将无序。

set(x) == set(y)

Documentation on ^{}

---

编辑：@mdwhatcott指出要检查重复项。set忽略这些，因此您需要一个类似的数据结构，该结构还可以跟踪每个列表中的项数。这称为a multiset；标准库中的最佳近似值是a ^{}：

>>> import collections
>>> compare = lambda x, y: collections.Counter(x) == collections.Counter(y)
>>> 
>>> compare([1,2,3], [1,2,3,3])
False
>>> compare([1,2,3], [1,2,3])
True
>>> compare([1,2,3,3], [1,2,2,3])
False
>>> 

Answer 3

sorted(x) == sorted(y)

从这里复制：Check if two unordered lists are equal

我认为这是这个问题最好的答案，因为

1. 它比使用this answer中指出的计数器要好
2. x、 sort（）对x排序，这是一个副作用。sorted（x）返回一个新列表。