判断两个列表是否包含相同元素，不考虑顺序？

Question

抱歉问了个简单的问题，但我找不到答案。

当我比较两个列表时，我想知道它们是否“相等”，也就是说它们的内容是一样的，只是顺序不同。

例如：

x = ['a', 'b']
y = ['b', 'a']

我希望 x == y 的结果是 True。

Answer 1

这个方法看起来可以用，不过对于很大的列表来说可能会有点麻烦。

>>> A = [0, 1]
>>> B = [1, 0]
>>> C = [0, 2]
>>> not sum([not i in A for i in B])
True
>>> not sum([not i in A for i in C])
False
>>> 

但是，如果每个列表必须包含其他列表的所有元素，那么上面的代码就有问题了。

>>> A = [0, 1, 2]
>>> not sum([not i in A for i in B])
True

问题出现在当 len(A) != len(B) 的时候，在这个例子中，len(A) > len(B)。为了避免这个问题，你可以再加一个判断。

>>> not sum([not i in A for i in B]) if len(A) == len(B) else False
False

还有一件事，我用 timeit.repeat 来测试我的解决方案，条件和 Aaron Hall 在他帖子中使用的一样。正如我所怀疑的，结果让人失望。我的方法是最后一种。就是 set(x) == set(y) 这个。

>>> def foocomprehend(): return not sum([not i in data for i in data2])
>>> min(timeit.repeat('fooset()', 'from __main__ import fooset, foocount, foocomprehend'))
25.2893661496
>>> min(timeit.repeat('foosort()', 'from __main__ import fooset, foocount, foocomprehend'))
94.3974742993
>>> min(timeit.repeat('foocomprehend()', 'from __main__ import fooset, foocount, foocomprehend'))
187.224562545

Answer 2

如何判断两个列表的元素是否相同，不考虑顺序？

根据你的例子来看：

x = ['a', 'b']
y = ['b', 'a']

列表中的元素不会重复（它们是唯一的），而且是可以哈希的（像字符串和其他一些不变的Python对象都是可以的），最直接且计算效率最高的方法是使用Python内置的集合（set），这和你在学校学过的数学集合是类似的。

set(x) == set(y) # prefer this if elements are hashable

如果元素是可以哈希的，但不是唯一的，collections.Counter也可以用作多重集合，但它的速度要慢得多：

from collections import Counter
Counter(x) == Counter(y)

如果元素是可以排序的，建议使用sorted：

sorted(x) == sorted(y) 

这可以处理非唯一或不可哈希的情况，但速度可能会比使用集合慢很多。

实证实验

实证实验得出的结论是，应该优先使用set，然后是sorted。只有在需要其他功能，比如计数或进一步用作多重集合时，才选择Counter。

首先设置：

import timeit
import random
from collections import Counter

data = [str(random.randint(0, 100000)) for i in xrange(100)]
data2 = data[:]     # copy the list into a new one

def sets_equal(): 
    return set(data) == set(data2)

def counters_equal(): 
    return Counter(data) == Counter(data2)

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2)

然后进行测试：

>>> min(timeit.repeat(sets_equal))
13.976069927215576
>>> min(timeit.repeat(counters_equal))
73.17287588119507
>>> min(timeit.repeat(sorted_lists_equal))
36.177085876464844

所以我们看到，比较集合是最快的解决方案，而比较排序后的列表是第二快的。

Answer 3

你可以简单地检查一下包含x和y元素的多重集合是否相等：

import collections
collections.Counter(x) == collections.Counter(y)

这要求元素是可以被哈希的；运行时间是O(n)，其中n是列表的大小。

如果元素都是唯一的，你也可以转换成集合（运行时间是一样的，实际操作中可能会稍微快一点）：

set(x) == set(y)

如果元素不能被哈希，但可以排序，另一种选择（运行时间是O(n log n)）是：

sorted(x) == sorted(y)

如果元素既不能被哈希也不能排序，你可以使用以下辅助函数。请注意，这种方法会非常慢（O(n²)），一般情况下不应该在没有哈希和不可排序的元素的特殊情况下使用。

def equal_ignore_order(a, b):
    """ Use only when elements are neither hashable nor sortable! """
    unmatched = list(b)
    for element in a:
        try:
            unmatched.remove(element)
        except ValueError:
            return False
    return not unmatched