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

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

Python有一个内置的数据类型，用于存储（可哈希）事物的无序集合，称为set。如果将两个列表都转换为集合，则比较将无序。set(x) == set(y)有关文档 set编辑：@mdwhatcott指出您要检查重复项。set忽略这些，因此您需要一个类似的数据结构，该结构还可以跟踪每个列表中的项目数。这称为多集；标准库中的最佳近似值为collections.Counter：>>> 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 2

如果元素总是像您的示例中那样几乎被排序，则内建.sort()（timsort）应该很快：>>> a = [1,1,2]>>> b = [1,2,2]>>> a.sort()>>> b.sort()>>> a == bFalse如果您不想就地排序，可以使用sorted()。在实践中它可能永远是那么快collections.Counter()（尽管渐进O(n)时间是更好，然后O(n*log(n))进行.sort()）。测量它；如果重要的话。

Answer 3

您想查看它们是否包含相同的元素，但是不在乎顺序。您可以使用一组：>>> set(['one', 'two', 'three']) == set(['two', 'one', 'three'])True但是set对象本身仅包含每个唯一值的一个实例，并且不会保留顺序。>>> set(['one', 'one', 'one']) == set(['one'])True因此，如果跟踪重复项/长度很重要，那么您可能还需要检查长度：def are_eq(a, b):    return set(a) == set(b) and len(a) == len(b)