приведенные здесь, и ямы придумали другого,Быстрее(в обычных случаях) решение, хотя оно и не так элегантно.

Прежде всего, давайтеПосмотрим, насколько быстрыми являются предлагаемые решения:

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

Тот'больше чемтридцать пять раз быстрее, чем genxp!

Почему это работает? Сравнения, очевидно, занимают линейное время, поэтому похоже, что мы делаем гораздо больше работы, чем раньше ... и это 'правда, но это правдасделано на "С уровень "и, следовательно, в результате этот метод на самом деле быстрее.

Обратите внимание, что это как-токонкретная реализация " потому что реализации, такие как 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, 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. Использование байтов вместо строк Юникода не делаетзначительно изменить результаты