如何在Python中有效地比较两个无序列表（而不是集合）？

Question

a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]

a&；b应该被认为是相等的，因为它们有完全相同的元素，只是顺序不同

问题是，我的实际列表将由对象（我的类实例）组成，而不是整数

Answer 1

如果您知道这些项总是可散列的，那么可以使用Counter()，即O（n）
如果您知道项目总是可排序的，那么可以使用sorted()，它是O（n log n）

在一般情况下，您不能依赖于能够排序或拥有元素，因此您需要这样的回退，不幸的是O（n^2）

len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)

Answer 2

您可以对以下两种情况进行排序：

sorted(a) == sorted(b)

counting sort也可能更有效（但它要求对象是可散列的）

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True

Answer 3

O（n）：最好使用Counter()方法（如果对象是可散列的）：

def compare(s, t):
    return Counter(s) == Counter(t)

O（n log n）：下一个最佳方法是sorted()方法（如果您的对象是可排序的）：

def compare(s, t):
    return sorted(s) == sorted(t)

O（n*n）：如果对象既不可散列也不可排序，则可以使用相等：

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t