确定2个列表是否具有相同的元素,无论顺序如何？

Question

对不起这个简单的问题,但我很难找到答案.

当我比较2个列表时,我想知道它们是否"相等",因为它们具有相同的内容,但顺序不同.

例如:

x = ['a', 'b']
y = ['b', 'a']

我想x == y评价一下True.

Answer 1

您可以简单地检查具有x和y元素的多集合是否相等:

import collections
collections.Counter(x) == collections.Counter(y)

这要求元素可以清洗; 运行时将在O(n),n列表的大小在哪里.

如果元素也是唯一的,你也可以转换为集合(相同的渐近运行时,在实践中可能会快一点):

set(x) == set(y)

如果元素不可清除但可排序,则另一个替代方法(运行时O(n log n))

sorted(x) == sorted(y)

如果元素既不可清洗也不可排序,则可以使用以下辅助函数.请注意,它将非常慢(O(n²))并且通常不应在不可消除和不可移动元素的深奥情况之外使用.

def equal_ignore_order(a, b):
    """ Use only when elements are neither hashable nor sortable! """
    unmatched = list(b)
    for element in a:
        try:
            unmatched.remove(element)
        except ValueError:
            return False
    return not unmatched

Answer 2

确定2个列表是否具有相同的元素,无论顺序如何？

从你的例子中推断:

x = ['a', 'b']
y = ['b', 'a']

列表的元素不会重复(它们是唯一的)以及可散列的(字符串和其他某些不可变的python对象),最直接和计算效率最高的答案使用Python的内置集(它们在语义上类似于数学你可能在学校里学过的东西).

set(x) == set(y) # prefer this if elements are hashable

在元素是可散列但非唯一的情况下,它collections.Counter也在语义上作为多重集合工作,但它要慢得多:

from collections import Counter
Counter(x) == Counter(y)

更喜欢使用sorted:

sorted(x) == sorted(y) 

如果元素是可订购的.这将解释非唯一或不可清除的情况,但这可能比使用集合慢得多.

实证实验

实证实验的结论是,人们应该更喜欢set的话sorted.只有Counter在您需要其他内容(如计数或进一步使用作为多重集)时才选择.

首先安装:

import timeit
import random
from collections import Counter

data = [str(random.randint(0, 100000)) for i in xrange(100)]
data2 = data[:]     # copy the list into a new one

def sets_equal(): 
    return set(data) == set(data2)

def counters_equal(): 
    return Counter(data) == Counter(data2)

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2)

并测试:

>>> min(timeit.repeat(sets_equal))
13.976069927215576
>>> min(timeit.repeat(counters_equal))
73.17287588119507
>>> min(timeit.repeat(sorted_lists_equal))
36.177085876464844

因此,我们看到比较集是最快的解决方案,比较排序列表是第二快的.