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

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 == b

False

如果您不想就地排序，可以使用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)