如何有效地比较Python中的两个无序列表(而不是集合)？

Question

如何有效地比较Python中的两个无序列表(而不是集合)？a = [1, 2, 3, 1, 2, 3] b = [3, 2, 1, 3, 2, 1]A&B应该被认为是相等的，因为它们有完全相同的元素，只是顺序不同。问题是，我的实际列表将由对象(我的类实例)组成，而不是整数。

Answer 1

O(N)*计数器()方法是最好的(如果您的对象是可告诉您的)：

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

O(n对数n)*排序()方法次之(如果对象是可排序的)：

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

Answer 2

你可以对两者进行排序：

sorted(a) == sorted(b)

A 计数排序也可能更有效率(但它要求对象是可哈斯的)。

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

最好的方法是对列表进行排序和比较。(使用Counter)无法处理无法使用的对象。)对于整数来说，这很简单：

sorted(a) == sorted(b)

对于任意的对象，它会变得更加棘手。如果您关心对象标识，即同对象都在两个列表中，可以使用id()函数作为排序键。

sorted(a, key=id) == sorted(b, key==id)

(在Python2.x中，实际上不需要key=参数，因为可以将任何对象与任何对象进行比较。排序是任意的，但是稳定的，因此它可以很好地实现这个目的；不管对象的顺序是什么，只是两个列表的排序是相同的。然而，在Python 3中，在许多情况下不允许比较不同类型的对象-例如，不能将字符串与整数进行比较-因此，如果要拥有不同类型的对象，最好显式使用对象的ID。

如果要比较列表中的对象价值，另一方面，首先您需要定义对象的“值”意味着什么。然后，您将需要一些方法来提供作为键(对于Python 3，作为一个一致的类型)。对于许多任意对象来说，一种可能的方法是根据它们的repr()..当然，这会浪费很多额外的时间和内存。repr()用于大列表的字符串等等。

sorted(a, key=repr) == sorted(b, key==repr)

如果对象都是您自己的类型，则可以定义__lt__()使对象知道如何将自己与他人进行比较。然后您就可以对它们进行排序，而不必担心key=参数。当然你也可以定义__hash__()和使用Counter，这会更快。