python - 指向结果的Python字符串比较

Question

我试图比较 2 1000 字节的字符串，并想知道差异究竟从哪里开始，即；字符串与哪个字节不同..有什么函数可以确定它吗？

Answer 1

也许使用next加上发电机？

next(idx for idx,c in enumerate(your_string1) if c != your_string2[idx])

这将为您提供差异开始的索引，StopIteration如果它们相等则提高。

它甚至可能稍微优雅一点itertools.izip：

next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)

例子：

>>> from itertools import izip
>>> s1 = 'stop at the bus'
>>> s2 = 'stop at the car'
>>> next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
12
>>> s1[12]
'b'
>>> s2[12]
'c'

Answer 2

我试图测试这里给出的答案，并且我想出了另一个更快（在通常情况下）的解决方案，即使它不那么优雅。

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

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 字符串不会显着改变结果}

Answer 3

for i, (x, y) in enumerate(zip(a, b)):
    if x != y:
        print('First index where strings are different:', i)
        break
else:
    print('Strings are identical.')

在 Python 2.x 中，zip()返回元组列表，而不是迭代器。正如 gnibbler 指出的那样，如果您使用的是 Python 2.x，则可能值得您使用izip而不是zip（izip返回一个很好的、内存高效的迭代器，避免一次评估所有值）。正如我在评论中所说，在 Python 3 中，izip已重命名zip，旧版本zip已不复存在。

Answer 4

如果你想要更复杂的东西，你可以看看SequenceMatcher

它有点毛茸茸，但非常强大。如果您只是想回答您的问题，那么：

from  difflib import SequenceMatcher

s1 = 'stop at the bus'
s2 = 'stop at the car'

s = SequenceMatcher(None, s1, s2)

print s.get_matching_blocks()[0].size

返回解决方案:)

但是如果你想要所有的比赛：

小例子：

from  difflib import SequenceMatcher

s1 = 'stop at the bus'
s2 = 'stop at the car'

s = SequenceMatcher(None, s1, s2)

print s.get_matching_blocks()

返回

[Match(a=0, b=0, size=12), Match(a=15, b=15, size=0)]

这意味着您的字符串中最长的匹配大小为 12，并且从开头 (0) 开始。但是还有另一场比赛，从 s1[15] 开始，大小为 0 。. .

对于像你这样的大字符串，这可能非常有趣。:)

Answer 5

>>> s1 = 'stop at the bus'
>>> s2 = 'stop at the car'
>>> import difflib
>>> next(difflib.SequenceMatcher(a=s1, b=s2).get_matching_blocks())
Match(a=0, b=0, size=12)

这意味着第一个匹配块的长度为 12 个字符。

如果 a 或 b 不为 0，则字符串从一开始就不同

Answer 6

这可能有点矫枉过正，但由于您似乎关心速度，您可以考虑使用 numpy. 可能需要改进（由于某种原因，内联对我来说产生了 25 我们的差异），但这是第一步：

>>> def diff_index(s1, s2):
...     s1 = numpy.fromstring(s1, dtype=numpy.uint8)
...     s2 = numpy.fromstring(s2, dtype=numpy.uint8)
...     return (~(s1 == s2)).nonzero()[0][0]
... 
>>> base = string.lowercase * 385
>>> s1 = base + 'a'
>>> s2 = base + 'z'
>>> diff_index(s1, s2)
10010

对于最后的差异，这比基因快得多：

>>> %timeit next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
1000 loops, best of 3: 1.46 ms per loop
>>> %timeit diff_index(s1, s2)
10000 loops, best of 3: 87.6 us per loop

一开始的差异要慢得多...

>>> s1 = 'a' + base
>>> s2 = 'z' + base
>>> %timeit next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
100000 loops, best of 3: 2.12 us per loop
>>> %timeit diff_index(s1, s2)
10000 loops, best of 3: 87.5 us per loop

但平均而言，它胜出一个数量级：

>>> s1 = base[:5000] + 'a' + base[5000:]
>>> s2 = base[:5000] + 'z' + base[5000:]
>>> %timeit next(idx for idx,(c1,c2) in enumerate(izip(s1,s2)) if c1 != c2)
1000 loops, best of 3: 724 us per loop
>>> %timeit diff_index(s1, s2)
10000 loops, best of 3: 87.2 us per loop

但是，如果速度不是问题，那么我个人会选择mgilson的答案。