指向结果的Python字符串比较

Question

我试图比较2个1000字节的字符串，并想知道差异的确切位置，即；字符串与哪个字节不同。.是否有任何函数可以确定它？

Answer 1

我试图测试此处给出的答案，并且提出了另一个 更快 （通常情况下）的解决方案，尽管它不太优雅。

首先，让我们看看所提出的解决方案有多快：

In [15]: def check_genexp(a, b):
    ...:     return next(idx for idx, c in enumerate(a) if c != b[idx])

In [16]: %timeit check_genexp("a"*9999 + "b", "a"*9999 + "c")
1000 loops, best of 3: 1.04 ms per loop

In [17]: from difflib import SequenceMatcher

In [18]: def check_matcher(a, b):
    ...:     return next(SequenceMatcher(a=a, b=b).get_matching_blocks())
    ...:

In [19]: %timeit check_matcher("a"*9999+"b", "a"*9999+"c")
100 loops, best of 3: 11.5 ms per loop

如您所见，genexp比快很多difflib，但这可能是由于SequenceMatcher它比查找第一个非等号字符要好得多。

现在，我们如何加快速度？好吧，我们可以使用“二进制搜索”
！！！这个想法是，如果两个字符串不相等，则前半部分是不同的，或者后半部分是不同的（或两者都不同），但是在那种情况下，我们只关心前半部分，因为我们想要第一个不同的索引。

因此，我们可以执行以下操作：

def binary_check(a, b):
    len_a, len_b = len(a), len(b)
    if len_a == len_b:
        return binary_check_helper(a, b)
    min_length, max_length = min(len_a, len_b), max(len_a, len_b)
    res = binary_check_helper(a[:min_length], b[:min_length])
    return res if res >= 0 else min_length

def binary_check_helper(a, b):
    if a == b:
        return -1
    length = len(a)

    if length == 1:
        return int(a[0] == b[0])
    else:
        half_length = length // 2
        r = binary_check_helper(a[:half_length], b[:half_length])
        if r >= 0:
            return r
        r = binary_check(a[half_length:], b[half_length:])
        if r >= 0:
            return r + half_length
        return r

结果：

In [34]: %timeit binary_check("a"*9999 + "b", "a"*9999 + "c")
10000 loops, best of 3: 28.4 µs per loop

这比genexp快 三十五倍 ！

为什么这样有效？比较显然需要花费线性时间，因此看起来我们要比以前做更多的工作……这确实是正确的，但它是在“ C级别”完成的，因此结果是该方法实际上更快。

请注意，这某种程度上是“特定于实现的”，因为诸如PyPy之类的实现可能会将genexp优化为单个C-
for循环，这将击败任何事物。在Jython或IronPython之类的实现上也 可能 比CPython慢​​很多。

该方法具有与其他方法相同的渐近复杂度，即O（n）。字符串最多会分成两半，log_2(n)并且每次进行相等性测试时都需要花费线性时间。乍一看，它似乎是Θ（n * logn）算法，但事实并非如此。递归公式为：

T(n) = T(n//2) + Θ(n) = Σ_{i=0}^{logn}(n/2^i)
     = Θ(n(1 + 1/2 + 1/4 + ...)) <= Θ(2n) = Θ(n)

更多结果：

In [37]: %timeit binary_check("a"*10**6 + "b", "a"*10**6 + "c")
100 loops, best of 3: 2.84 ms per loop

In [38]: %timeit check_genexp("a"*10**6 + "b", "a"*10**6 + "c")
10 loops, best of 3: 101 ms per loop

In [39]: %timeit binary_check(15 * "a"*10**6 + "b", 15 * "a"*10**6 + "c")
10 loops, best of 3: 53.3 ms per loop

In [40]: %timeit check_genexp(15 * "a"*10**6 + "b", 15 * "a"*10**6 + "c")
1 loops, best of 3: 1.5 s per loop

如您所见，即使使用巨大的字符串，此方法仍然快30倍。

注意： 该解决方案的缺点是它是ϴ（n）而不是O（n），即，它 始终 读取 整个 字符串以返回结果。即使第一个字符已经不同。事实上：

In [49]: a = "b" + "a" * 15 * 10**6
    ...: b = "c" + "a" * 15 * 10**6
    ...:

In [50]: %timeit binary_check(a, b)
100 loops, best of 3: 10.3 ms per loop

In [51]: %timeit check_genexp(a, b)
1000000 loops, best of 3: 1.3 µs per loop

这是预料之中的。但是，与显式循环相比，此解决方案只需花费很少的精力即可变得更加高效：

In [59]: a = "a" * 2 * 10**5 + "b" + "a" * 15*10**6
    ...: b = "a" * 2 * 10**5 + "c" + "a" * 15*10**6

In [60]: %timeit check_genexp(a, b)
10 loops, best of 3: 20.3 ms per loop

In [61]: %timeit binary_check(a, b)
100 loops, best of 3: 17.3 ms per loop

根据这个简单的基准，对于大字符串，如果差异远大于总长度的 1.3％ ，则二进制检查会更好。

也可以引入一些启发式方法。例如，如果两个字符串的最小长度大于某个截断值，则首先仅检查该截断处的前缀是否不同，如果是，则不能忽略此后的所有内容，从而避免比较整个字符串。这可以轻松实现：

def binary_check2(a, b, cutoff=1000):
    len_a, len_b = len(a), len(b)
    if min(len_a, len_b) > cutoff:
        small_a, small_b = a[:cutoff], b[:cutoff]
        if small_a != small_b:
            return binary_check_helper(a[:cutoff], b[:cutoff])
    # same as before

根据应用程序，您可以选择一个使平均时间最短的截止时间。在任何情况下，这都是一种临时启发式方法，可能会奏效，也可能无法奏效，因此，如果您处理的字符串 很长
且仅带有短的公共前缀，则应使用“快速失败”算法genexp。

在python3.4上执行的计时。使用字节代替unicode字符串不会显着改变结果