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

Question

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

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

问题是,我的实际列表将包含对象(我的类实例),而不是整数.

Answer 1

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

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

如果你知道这些项目总是可以清洗,你可以使用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 4

如果要在测试上下文中执行比较，请使用assertCountEqual(a, b)( py>=3.2) 和assertItemsEqual(a, b)( 2.7<=py<3.2)。

也适用于不可哈希对象的序列。

Answer 5

最好的方法是对列表进行排序并进行比较.(使用Counter不适用于不可清除的对象.)这对于整数来说很简单:

sorted(a) == sorted(b)

使用任意对象会变得有点棘手.如果您关心对象标识,即两个列表中是否存在相同的对象,则可以将该id()函数用作排序键.

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

(在Python 2.x中,您实际上并不需要key=参数,因为您可以将任何对象与任何对象进行比较.排序是任意的但是稳定,因此它可以正常工作;对象的顺序无关紧要但是,只有两个列表的排序相同.但是在Python 3中,在许多情况下不允许比较不同类型的对象 - 例如,你不能将字符串与整数进行比较 - 所以如果你有对象各种类型,最好明确使用对象的ID.)

另一方面,如果要按值比较列表中的对象,首先需要定义"值"对于对象的含义.然后你需要一些方法来提供它作为一个键(对于Python 3,作为一致的类型).对许多任意对象起作用的一种可能方法是按它们排序repr().当然,这可能会浪费大量额外的时间和内存构建repr()大型列表的字符串等等.

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

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

Answer 6

如果您必须在测试中执行此操作：https : //docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual(first, second, msg=None)

测试该序列首先包含与第二个相同的元素，而不管它们的顺序如何。如果他们不这样做，则会生成一条错误消息，列出序列之间的差异。

比较第一个和第二个时不会忽略重复元素。它验证每个元素在两个序列中是否具有相同的计数。等效于： assertEqual(Counter(list(first)), Counter(list(second))) 但也适用于不可散列对象的序列。

3.2 版中的新功能。

或在 2.7：https : //docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

在测试之外，我会推荐这种Counter方法。