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

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

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

事情是,我的实际列表将由对象(我的类实例),而不是整数。

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 

你可以sorting两个:

 sorted(a) == sorted(b) 

计数sorting也可能更高效(但要求对象可哈希)。

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

如果你知道这些项目总是可以被哈希的,你可以使用一个Counter() ,它是O(n)
如果你知道这些项目总是可sorting的,你可以使用sorted() ,它是O(n log n)

在一般情况下,你不能依靠能够sorting,或有元素,所以你需要像这样的后备,不幸的是O(n ^ 2)

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

做到这一点的最好方法是对列表进行sorting并进行比较。 (使用Counter不能处理不可哈希的对象。)这对于整数来说很简单:

 sorted(a) == sorted(b) 

它与任意对象有点棘手。 如果你关心对象的身份,也就是两个列表中是否有相同的对象,你可以使用id()函数作为sorting关键字。

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

(在Python 2.x中,实际上并不需要key=参数,因为您可以将任何对象与任何对象进行比较。sorting是任意的但是稳定的,所以对于这个目的它可以很好地工作;不pipe它的顺序如何但是在Python 3中,在许多情况下不允许比较不同types的对象,例如,你不能比较string和整数,所以如果你愿意的话,有各种types的对象,最好明确地使用对象的ID。)

如果你想用来比较列表中的对象,另一方面,首先你需要定义对象的“值”是什么意思。 然后你将需要一些方法来提供这个作为一个键(和Python 3,作为一个一致的types)。 一个可能适用于大量任意对象的方法是通过repr()进行sorting。 当然,这可能会浪费大量额外的时间和内存,为大型列表build立repr()string等等。

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

如果对象都是你自己的types,你可以在它们上定义__lt__() ,以便对象知道如何比较自己和其他对象。 然后你可以对它们进行sorting而不用担心key=参数。 当然你也可以定义__hash__()并使用Counter ,这会更快。

让a,b列出

 def ass_equal(a,b): try: map(lambda x: a.pop(a.index(x)), b) # try to remove all the elements of b from a, on fail, throw exception if len(a) == 0: # if a is empty, means that b has removed them all return True except: return False # b failed to remove some items from a 

没有必要使他们可以sorting或sorting。

我希望下面的一段代码可以在你的情况下工作: –

 if ((len(a) == len(b)) and (all(i in a for i in b))): print 'True' else: print 'False' 

这将确保列表ab中的所有元素都是相同的,不pipe它们是否在相同的顺序。

为了更好的理解,请参考我在这个问题上的答案

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

对不可对象序列也起作用。

https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual(第一,第二,味精=无)

testing序列首先包含与第二个相同的元素,而不pipe它们的顺序如何。 如果没有,则会产生列出序列之间差异的错误消息。

比较第一个和第二个时,重复的元素不会被忽略。 它validation每个元素在两个序列中是否具有相同的计数。 等同于:assertEqual(Counter(list(first)),Counter(list(second))),但是也可以处理不可对象序列。

3.2版本的新function

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

如果列表包含不可哈希的项目(例如对象列表),则可以使用Counter类和id()函数,例如:

 from collections import Counter ... if Counter(map(id,a)) == Counter(map(id,b)): print("Lists a and b contain the same objects")