如何高效比较两个无序列表（而不是集合）？

Question

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

考虑到a和b具有完全相同的元素，只是顺序不同，因此应被视为相等。

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

- johndir

---

物体是如何进行比较的？ - Marcelo Cantos

真实列表的预期大小是多少？将要比较的列表大小是否相当或非常不同？您是否预计大多数列表将匹配还是不匹配？ - Dmitry B.

可以先检查 len()。 - greybeard

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

- Raymond Hettinger

---

谢谢。我将每个对象转换为字符串，然后使用了Counter()方法。 - johndir

对于短列表而言，大 O 分析通常不相关，因为时间复杂度受到常量因子的支配。对于较长的列表，我怀疑你的基准测试存在问题。对于包含 100 个整数并且每个整数重复出现 5 次的列表，我得到了如下结果：排序需要 127 微秒，Counter 需要 42 微秒（约快 3 倍）。当有 1,000 个整数并且每个整数重复出现 5 次时，Counter 的速度是排序的 4 倍。执行此操作的命令为："python3.6 -m timeit -s 'from collections import Counter' -s 'from random import shuffle' -s 't=list(range(100)) * 5' -s 'shuffle(t)' -s 'u=t[:]' -s 'shuffle(u)' 'Counter(t)==Counter(u)'"。 - Raymond Hettinger

不用了，我对调试无意义的时间脚本没有太多兴趣。这里涉及到很多方面（纯Python对C代码、在随机数据与半有序数据上应用timsort算法、不同版本的具体实现细节、数据中重复项的数量等）。 - Raymond Hettinger

@RaymondHettinger你说Counter方法的时间复杂度是O(n)，但是对于在计数器字典中插入键/值呢？嗯，我想这会使它变成O(n + log(n))。 - Jean-François Fabre

@Jean-FrançoisFabre说：“O(n + log(n))”可以简化为“O(n)”，因为n是更高的复杂度级别。” - StriplingWarrior

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

- Mark Byers

---

计数器确实使用了哈希，但对象本身并不是不能被哈希化的。只需实现一个合理的__hash__方法即可，但对于集合类可能是不可能的。 - Jochen Ritzel

sorted也不是万能的，比如复数sorted([0, 1j])。 - John La Rooy

sorted() 也不能用于集合，如果比较运算符已被重载用于子集/超集测试。 - Raymond Hettinger

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)

- John La Rooy

Answer 4

如果你需要在测试中做到以下内容： https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual assertCountEqual(first, second, msg=None) 测试序列first是否包含与second相同的元素，无论其顺序如何。如果不相同，则会生成列出序列之间差异的错误消息。

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

自版本3.2新增。

或者在2.7中： https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual 除了测试外，我建议使用Counter方法。

- cleder

---

这对 jarekwg 的回答 有什么补充？ - greybeard

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更快地完成操作。

- kindall

Answer 6

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

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

- jarekwg

---

哇，伙计！这不直观 - 名称可能会暗示它只是 len(a) == len(b) 而不是 MagicCounter(a) == MagicCounter(b)，其中 MagicCounter 是一个可以处理不可哈希对象的 Counter... - Tomasz Gandor

Answer 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")

- Mars

Answer 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

不需要使它们可哈希或排序。

- Umur Kontacı

---

是的，但正如其他几位发帖者所指出的那样，这是O(n**2)的，因此只有在其他方法不起作用时才应该使用。它还假定a支持pop(可变)和index(序列)。Raymond的假设两者都不支持，而gnibbler的则仅假设为序列。 - agf

Answer 9

我希望以下代码能在你的情况下起作用：

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

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

为了更好地理解，请参考this question中我的答案。

- Pabitra Pati

Answer 10

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的值，以找出它们是否匹配。

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

- Induane

---

_list_eq([0, 0, 1] [0, 1, 1]) - greybeard

哈哈！说得好！ - Induane

已更正。好发现！ - Induane