如何高效比较两个无序列表（非集合）？

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) 稍慢一些，但还是比较快。

在一般情况下，你不能保证所有的项目都可以排序或者哈希，所以你需要一个备用的方法来处理这些情况，但遗憾的是，这种方法的效率是 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)

一种叫做计数排序的方法也可能更有效（但它需要对象是可哈希的）。

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