指向结果的Python字符串比较

概述我试图比较2 1000字节的字符串,并想知道差异的确切开始,即;字符串从哪个字节不同..是否有任何函数来确定它？ 我试图测试这里给出的答案,我想出了另一个更快的(通常情况下)解决方案,即使它不那么优雅. 首先,让我们看看提议的解决方案有多快： In [15]: def check_genexp(a, b): ...: return next(idx for idx, c in en 我试图比较2 1000字节的字符串,并想知道差异的确切开始,即;字符串从哪个字节不同..是否有任何函数来确定它？解决方法 我试图测试这里给出的答案,我想出了另一个更快的(通常情况下)解决方案,即使它不那么优雅.

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

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 loopIn [17]: from difflib import SequenceMatcherIn [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_lengthdef 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 loopIn [38]: %timeit check_genexp("a"*10**6 + "b","a"*10**6 + "c")10 loops,best of 3: 101 ms per loopIn [39]: %timeit binary_check(15 * "a"*10**6 + "b",15 * "a"*10**6 + "c")10 loops,best of 3: 53.3 ms per loopIn [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 loopIn [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**6In [60]: %timeit check_genexp(a,b)10 loops,best of 3: 20.3 ms per loopIn [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字符串不会显着改变结果

总结

以上是内存溢出为你收集整理的指向结果的Python字符串比较全部内容，希望文章能够帮你解决指向结果的Python字符串比较所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。