优雅的比较序列的方法

Question

Python是否提供了一种优雅的方式来检查不同类型的序列的"相等性"? 以下方法可以实现，但对于Python代码来说似乎冗长又不够优美:

def comp1(a, b):
    if len(a) != len(b):
        return False
    for i, v in enumerate(a):
        if v != b[i]:
            return False
    return True

以下代码稍微短一些，但效率较低因为创建了第三个序列：

def comp2(a, b):
    for l, r in map(None, a, b):
        if l != r:
            return False
    return True

将这些示例之一硬塞到列表推导式中并不是我正在寻找的方法。

编辑：理想情况下，我正在寻找一种在比较过程中不创建另一个序列的解决方案。

- schickb

Answer 1

将两个序列都转换为列表，然后使用内置的列表比较。这应该足够了，除非你的序列真的很大。

list(a) == list(b)

编辑：

schickb进行的测试表明，使用元组略微更快：

tuple(a) == tuple(b)

- Ayman Hourieh

---

那会创建两个附加列表。由于列表可能很长，我希望避免这种情况。 - schickb

@schickb：你指的时间是多久？根据你的帖子标题和第一句话，优雅性应该是首要考虑因素，效率则是额外加分项。对我而言，转换为（新）列表无疑是最优雅、最“程序员高效”的解决方案。 - John Y

@John，是的，在进行了更多测试后我同意。这个解决方案实际上比枚举循环还要快得多。然而，我相信这在某些序列大小上会发生改变。即使tuple(a) == tuple(b)似乎更好，但我仍将标记此为答案。 - schickb

@schickb - 我在答案中添加了元组方法。 - Ayman Hourieh

这个解决方案纯粹浪费 CPU 时间和内存：首先迭代可迭代对象并在内存中累加结果，然后再迭代累加的结果以进行比较。更不用说可迭代对象在第一个元素处就可能不同。想象一下在昂贵计算的内部循环中使用此解决方案的情况。 - Alexey

Answer 2

你可以使用以下方式来确定任意两个可迭代对象（字符串、元组、列表，甚至自定义序列）的相等性，而无需创建和存储重复的列表：

all(x == y for x, y in itertools.izip_longest(a, b))

请注意，如果两个可迭代对象长度不同，则较短的一个将填充None。换句话说，它将考虑[1, 2, None]等于(1, 2)。

编辑：正如Kamil在评论中指出的那样，izip_longest仅适用于Python 2.6。然而，该函数的文档也提供了一种备用实现，可向后兼容至2.3。

编辑2：在几台不同的计算机上测试后，发现这种方法仅在某些情况下比list(a) == list(b)更快，我无法分离出这些情况。大多数情况下，它需要约七倍的时间。但是，我还发现tuple(a) == tuple(b)始终至少比list版本快两倍。

- Ben Blank

---

@schickb - 不是这样的，那是一个生成器，而不是列表推导式。它创建了一个生成器对象，只有在准备好发出每个元素时才会创建它。 - Ben Blank

@Ben和Vili：比第三个序列还要糟糕。每个条目都需要一个函数调用。 - schickb

这个解决方案提供了比已接受的方案更好的惰性求值（短路）。即使是对于小序列，如果计算每个元素不是微不足道的，这个解决方案也可能比将其转换为列表/元组的方案快得多。 - rafak

@rafak — 我确信Python内置的列表/元组比较也会尽早退出，而不是在出现不匹配后继续比较。我不认为这种技术在任何情况下都比已接受的解决方案更快。 :-) - Ben Blank

@BenBlank 在 Python 中，比较操作会进行短路优化，但是使用 Python 的 list() 构造函数仍然会创建整个列表。因此，如果你有一个巨大的列表（数百万项）并且它们在前面部分不同，那么生成器方法将更快。 - max

Answer 3

除了创建临时列表/元组使用的额外内存之外，当不等式在序列中早期发生时，这些答案将输给短路生成器解决方案，适用于大型序列。

from itertools import starmap, izip
from operator import eq
all(starmap(eq, izip(x, y)))

更简洁地说，

from itertools import imap
from operator import eq
all(imap(eq, x, y))

一些来自IPython的基准测试结果。

x=range(1000)
y=range(1000); y[10]=0

timeit tuple(x) == tuple(y)
100000 loops, best of 3: 16.9 us per loop

timeit all(imap(eq, x, y))
100000 loops, best of 3: 2.86 us per loop

- John La Rooy

---

这是当列表不小且早期元素有非平凡机会不同的最佳答案。但时间非常奇怪。在Python 3.5下（当然使用map和zip），从50百万长的列表x，y开始：starmap解决方案为2.5-2.6秒；map为3.5秒；而@Ben Blank解决方案（用zip替换izip_longest以保持一致性）为5秒。（我知道我们忽略长度不相等的列表，但无论如何。）这种性能差异非常奇怪，有什么想法吗？顺便说一句，tuple()需要2.0-2.1秒，仅比starmap稍快。 - max

@max，tuple很快。假设您有足够的内存并且预计序列通常是逐元素相等的，则转换为tuple将比生成器解决方案更快（至少对于此时的CPython）。 - John La Rooy

当然，我知道，但是我在想为什么你的 starmap 比 map 或 @Ben Blank 的解决方案要快那么多。（实际上，你的 starmap 几乎和元组一样快，这对我来说真的很出乎意料。） - max

Answer 4

看起来tuple(a) == tuple(b)是最好的选择。或者在它们经常有不同长度的情况下，可以使用带有先前len检查的元组比较。这确实会创建额外的列表，但除了对于真正巨大的列表可能会有问题以外，希望不会有太大问题。以下是我对各种建议的比较：

import timeit

tests = (
'''
a=b=[5]*100
''',

'''
a=[5]*100
b=[5]*3
''',

'''
a=b=(5,)*100
''',

'''
a=b="This on is a string" * 5
''',

'''
import array
a=b=array.array('B', "This on is a string" * 5)
'''
)

common = '''import itertools
def comp1(a, b):
    if len(a) != len(b):
        return False
    for i, v in enumerate(a):
        if v != b[i]:
            return False
    return True'''

for i, setup in enumerate(tests):
    t1 = timeit.Timer("comp1(a, b)", setup + common)
    t2 = timeit.Timer("all(x == y for x, y in itertools.izip_longest(a, b))", setup + common)
    t3 = timeit.Timer("all([x == y for x, y in itertools.izip_longest(a, b)])", setup + common)
    t4 = timeit.Timer("list(a) == list(b)", setup + common)
    t5 = timeit.Timer("tuple(a) == tuple(b)", setup + common)

    print '==test %d==' % i
    print '   comp1: %g' % t1.timeit()
    print ' all gen: %g' % t2.timeit()
    print 'all list: %g' % t3.timeit()
    print '    list: %g' % t4.timeit()
    print '   tuple: %g\n' % t5.timeit()

以下是结果：

==test 0==
   comp1: 27.8089
 all gen: 31.1406
all list: 29.4887
    list: 3.58438
   tuple: 3.25859

==test 1==
   comp1: 0.833313
 all gen: 3.8026
all list: 33.5288
    list: 1.90453
   tuple: 1.74985

==test 2==
   comp1: 30.606
 all gen: 31.4755
all list: 29.5637
    list: 3.56635
   tuple: 1.60032

==test 3==
   comp1: 33.3725
 all gen: 35.3699
all list: 34.2619
    list: 10.2443
   tuple: 10.1124

==test 4==
   comp1: 31.7014
 all gen: 32.0051
all list: 31.0664
    list: 8.35031
   tuple: 8.16301

编辑：增加了几个测试。这是在一台搭载AMD 939 3800+和2GB内存的计算机上运行的。使用的操作系统是Linux 32位，Python版本为2.6.2。

- schickb

---

现在使用Psyco运行所有相同的测试。 - Brian

你的列表很简单...如果每个元素都是一个密集计算任务，那么它可能不是更好的选择。 - rafak

Answer 5

我认为当两个序列都是list类型时，特殊处理是一个好主意。比较两个列表比将它们转换为元组更快（且更节省内存）。

如果a或b不是列表，则两者都会转换为tuple。如果一个或两个已经是元组，则没有开销，因为在这种情况下tuple()只返回对原始对象的引用。

def comp(a, b):
    if len(a) != len(b):
        return False
    if type(a) == type(b) == list:
        return a == b
    a = tuple(a)
    b = tuple(b)
    return a == b

- John La Rooy

Answer 6

既然您在引号中使用了“equality”这个词，我假设您想知道这些列表如何相同以及它们的不同之处。请查看difflib，其中包含一个SequenceMatcher类：

    sm = difflib.SequenceMatcher(None, a, b)
    for opcode in sm.get_opcodes():
        print "    (%s %d:%d %d:%d)" % opcode

你将会得到一系列描述差异的序列。将其转换为类似于diff的输出相当简单。

- Joel Bender

Answer 7

这可能不是很高效，但看起来很时髦：

def cmpLists(a, b):
    return len(a) == len(b) and (False not in [a[i] == b[i] for i in range(0,len(a)])

我不知道Ben提到的“all”函数，但也许你可以使用它来代替“False not in”。

- Smashery

Answer 8

这段“函数式”的代码应该足够快速和通用，适用于所有目的。

# python 2.6 ≤ x < 3.0
import operator, itertools as it

def seq_cmp(seqa, seqb):
    return all(it.starmap(operator.eq, it.izip_longest(seqa, seqb)))

如果使用 Python 2.5，则使用此处中 izip_longest 的定义。

- tzot

---

seq_cmp((0,1), [0,1, None]) 将返回 true。使用 fillvalue=object() 以确保不会将 fillvalue 与其他内容匹配。 - Ivan Klass