指向结果的Python字符串比较

我试图测试这里给出的答案,我想出了另一个更快的(通常情况下)解决方案,即使它不那么优雅.

首先,让我们看看提议的解决方案有多快：

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

正如你所看到的那样,即使使用大字符串,这种方法仍然快了大约三十倍.

注意：该解决方案的缺点是它是Θ(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,best of 3: 17.3 ms per loop

根据这个简单的基准测试,如果差异超过总长度的约1.3％,则使用大字符串,二进制检查更好.

也可以引入一些启发式方法.例如,如果两个字符串的最小长度大于某个截止值,则首先只检查该截止值的前缀是否不同,如果它们不能忽略之后的所有内容,从而避免比较整个字符串.这可以通过以下方式实现：

def binary_check2(a,b,cutoff=1000):
    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

根据应用程序,您可以选择最小化平均时间的截止值.
在任何情况下,这是一个特殊的启发式方法,可能会或可能不会很好,所以如果你只处理只有很短公共前缀的非常长的字符串,你应该使用“fail-fast”算法,就像genexp方法一样.

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