2 1000 バイトの文字列を比較しようとしていますが、違いがどこから始まるのかを正確に知りたいと考えています。文字列がどのバイトから異なるか..それを判断する関数はありますか?
6 に答える
9
たぶん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'
于 2012-10-11T13:21:18.723 に答える
4
私はここで与えられた答えをテストしようとしました、そして私はそれがあまりエレガントではありませんが、他のより速い（通常の場合）解決策を思いつきました。
まず、提案されたソリューションの速度を見てみましょう。
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、最初の等しくない文字を見つけるよりもはるかに多くのことを行うという事実によるものです。
さて、どうすれば物事をスピードアップできますか？さて、「二分探索」が使えます!!! 2つの文字列が等しくない場合、前半が異なるか、後半が異なる（または両方ですが、その場合は、最初の異なるインデックスが必要なので、前半のみを考慮します）。
したがって、次のようなことができます。
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よりも35倍以上高速です。
なぜこれが機能するのですか？比較には明らかに線形時間がかかるため、以前よりもはるかに多くの作業を行っているように見えます...実際にはそうですが、「経営幹部」レベルで行われているため、この方法の方が実際には高速です。
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倍高速です。
注：このソリューションの欠点は、O（n）ではなくϴ（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％を超える場合は、バイナリチェックの方が適しています。
いくつかのヒューリスティックを導入することも可能です。たとえば、2つの文字列の最小の長さが特定のカットオフ値よりも大きい場合、最初にそのカットオフのプレフィックスが異なるかどうかを確認するだけです。異なる場合は、その後すべてを無視できないため、文字列全体を比較することは避けられます。これは簡単に実装できます。
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文字列の代わりにバイトを使用しても、結果は大きく変わりません。
于 2012-10-11T15:26:17.950 に答える
2
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。ただし、コメントで述べたように、Python 3 では名前が変更され、古いものはなくなりました。zipizipizipzipzip
于 2012-10-11T13:23:56.913 に答える
2
もっと複雑なものが必要な場合は、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 の別の一致があります。. .
あなたのような大きな文字列の場合、これは非常に興味深いことです。:)
于 2012-10-11T13:35:54.397 に答える
1
>>> 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でない場合、文字列は最初とは異なります
于 2012-10-11T13:38:05.703 に答える
1
これはやり過ぎかもしれませんが、速度を気にしているように見えるので、numpy の使用を検討できます。おそらく改善の余地があります (何らかの理由でインライン化によって 25 us の差が生じました) が、これは最初のステップです。
>>> 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の回答を使用します。
于 2012-10-11T15:40:10.183 に答える