如何有效地比较两个无序列表（不是集合）？-IT科技

摘要：问题描述：a = [1, 2, 3, 1, 2, 3] b = [3, 2, 1, 3, 2, 1] a 和 b 应该被视为相等，因为它们具有完全相同的元素，只是顺序不同。问题是，我的实际列表将由对象（我的类实例）组成，而不是整数。解决方案 1：O（n）：Counter（）方法是最好的（如果你的对象是可哈希的...

问题描述：

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

a 和 b 应该被视为相等，因为它们具有完全相同的元素，只是顺序不同。

问题是，我的实际列表将由对象（我的类实例）组成，而不是整数。

解决方案 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

解决方案 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

解决方案 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)

解决方案 4：

如果您必须在测试中执行此操作：
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方法。

解决方案 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，这样会更快。

解决方案 6：

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

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

解决方案 7：

如果列表包含不可散列的项目（例如对象列表），您可能能够使用Counter 类和 id() 函数，例如：

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

解决方案 8：

让 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

无需使它们可散列或对它们进行排序。

解决方案 9：

我希望下面的代码可以对你有用：-

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

这将确保两个列表中的所有元素a都是b相同的，无论它们的顺序是否相同。

为了更好地理解，请参阅我在这个问题中的回答

解决方案 10：

您可以编写自己的函数来比较列表。

让我们得到两个列表。

list_1=['John', 'Doe'] 
list_2=['Doe','Joe']

首先，我们定义一个空字典，统计列表项并写入字典。

def count_list(list_items):
    empty_dict={}
    for list_item in list_items:
        list_item=list_item.strip()
        if list_item not in empty_dict:
            empty_dict[list_item]=1
        else:
            empty_dict[list_item]+=1
    return empty_dict

之后，我们将使用以下函数比较两个列表。

def compare_list(list_1, list_2):
    if count_list(list_1)==count_list(list_2):
        return True
    return False
compare_list(list_1,list_2)

解决方案 11：

from collections import defaultdict

def _list_eq(a: list, b: list) -> bool:
    if len(a) != len(b):
        return False
    b_set = set(b)
    a_map = defaultdict(lambda: 0)
    b_map = defaultdict(lambda: 0)
    for item1, item2 in zip(a, b):
        if item1 not in b_set:
            return False
        a_map[item1] += 1
        b_map[item2] += 1
    return a_map == b_map

如果数据高度无序，排序可能会非常慢（当项目具有一定程度的有序性时，timsort 特别好）。对两者进行排序还需要完全迭代两个列表。

不需要改变列表，只需分配一个集合并执行左-->右成员资格检查，并计算沿途存在的每个项目的数量：

如果两个列表的长度不一样，您可以短路并False立即返回。
如果你点击列表中任何a不在列表中的项目，b你可以返回False
a_map如果您获取了所有项目，那么您可以比较和的值b_map以查看它们是否匹配。

这使得您可以在迭代两个列表之前在许多情况下进行短路。

解决方案 12：

插入这个：

def lists_equal(l1: list, l2: list) -> bool:
    """

    import collections
    compare = lambda x, y: collections.Counter(x) == collections.Counter(y)
    ref:
        - https://stackoverflow.com/questions/9623114/check-if-two-unordered-lists-are-equal
        - https://stackoverflow.com/questions/7828867/how-to-efficiently-compare-two-unordered-lists-not-sets
    """
    compare = lambda x, y: collections.Counter(x) == collections.Counter(y)
    set_comp = set(l1) == set(l2)  # removes duplicates, so returns true when not sometimes :(
    multiset_comp = compare(l1, l2)  # approximates multiset
    return set_comp and multiset_comp  #set_comp is gere in case the compare function doesn't work

解决方案 13：

在比较两个词典列表时，这对我有用：

def compare_lists(list_a, list_b):
    if len(list_a) != len(list_b):
        return False
    for item in list_a:
        if item not in list_b:
            return False
        if list_a.count(item) != list_b.count(item):
            return False
    for item in list_b:
        if item not in list_a:
            return False

    return True