Python3 長さが同じ文字列同士の比較で違いが何個あるか

Question

####やりたいこと
長さが同じ文字列同士の比較で違いが何個あるかを調べる効率的な方法を模索しています。
現状は愚直にfor文でループさせて1文字づつ比較しています。
何か別の方法で比較出来るやり方あればご教示頂ければと思います。
####試したこと
検索したキーワード：文字列　比較　差分　違い　
似たような質問の回答からcollectionsやCounterが使えないかと思ったのですが何文字目かの比較が必要なので断念しました。

def count_diff(q,a):
    lst_q = list(q)
    lst_a = list(a)
    len_q = len(lst_q)
    ng = 0
    for i in range(len_q):
        if lst_q[i] != lst_a[i]:
            ng += 1
    print('NG:',ng,q,a)

q = 'abcdefg'
a = 'abcdefg'
b = 'xbcdefg'
c = 'xbxdxfx'

count_diff(q,a)
count_diff(q,b)
count_diff(q,c)

出力結果
NG: 0 abcdefg abcdefg
NG: 1 abcdefg xbcdefg
NG: 4 abcdefg xbxdxfx

回答頂いたコードの実行速度比較：GitHub

Answer 1

この場合は、質問文のコードと同様に一文字ずつ処理すればそれで良いと思いますが……O(n)だし。アルゴリズム的な改善方法はないと思います（断言はできませんが）。

元のコードは無駄な処理が多く、オーバーヘッドが発生しているので、その分は改善できるでしょう。

import timeit

def count_diff1(q,a):
    """
    オリジナル
    """
    lst_q = list(q)
    lst_a = list(a)
    len_q = len(lst_q)
    ng = 0
    for i in range(len_q):
        if lst_q[i] != lst_a[i]:
            ng += 1
    return ng

def count_diff2(a,b):
    """
    コードを単純化
    """
    cnt = 0
    for c1,c2 in zip(a, b):
        if c1 != c2:
            cnt += 1
    return cnt


q = 'abcdefg'
a = 'abcdefg'
b = 'xbcdefg'
c = 'xbxdxfx'

print(count_diff1(q,a))
print(count_diff2(q,a))
print(timeit.timeit(lambda: count_diff1(q,a)))
print(timeit.timeit(lambda: count_diff2(q,a)))

print(count_diff1(q,b))
print(count_diff2(q,b))
print(timeit.timeit(lambda: count_diff1(q,b)))
print(timeit.timeit(lambda: count_diff2(q,b)))

print(count_diff1(q,c))
print(count_diff2(q,c))
print(timeit.timeit(lambda: count_diff1(q,c)))
print(timeit.timeit(lambda: count_diff2(q,c)))

""" =>
0
0
1.819975644000806
0.8293105610064231
1
1
1.9003565619932488
0.8559812610037625
4
4
2.127330388990231
0.9501454940182157
"""

倍程度改善します。

Comments

[opyon]

ありがとうございます。
実行速度計測して確認しました。
知らない書き方なので調べながらあれこれ試してみます。

[opyon]

今更なのですがzip関数調べてみたら超便利でした。
今まで知らずに定型文として使ってたことありましたが盲点でした^^;
今後使えるところあれば積極的に使いたいと思います。

[opyon]

もうひとつ今更で知らないことがありました。
for文で文字列変数をinで指定した時にループで回せるということです。
今まで毎回リストに変換してました(多分javaの癖だと思います)。

このような質問していいのか少し戸惑いながらでしたが派生的に他のことも知れてとても参考になりました。
ありがとうございました。

Answer 2

とりあえず簡潔な書き方を考えます。

def count_diff2(q, a):
    return sum(
        c1 != c2 for c1, c2 in zip(q, a)
    )

1文字ずつ比較しているのには変わりありませんが、
Pythonの機能に頼っている分、ほんの少しだけ実行効率が良いようです。

計測結果 (1000000回実行)

count_diff1 2.729970581829548
count_diff2 2.3848468139767647

計測用コード Wandbox

Comments

[hayataka2049]

私もそれ試したら、遅かったので没にしました
無駄に0が加算されるので、ifの方が速いってことかなと

[LouiS0616]

かもしれませんね。
sum(1 for c1, c2 in zip(q, a) if c1 != c2) にしたら少しだけ改善されました。

それでも hayataka2049 さんの count_diff2 にはかないませんが。
シンプルイズベストってことでしょうね。

[opyon]

ありがとうございます。
処理速度はさほど変わらないのにスマートな書き方で勉強になります。

Answer 3

解決済みですので、参考まで。

結局のところ、遅くなっている原因が繰り返し処理にあるだとすれば、numpyを使って一括処理しようというものです。

import numpy as np

ar_lst_q = np.array(lst_q)  # arrayに変換
ar_lst_a = np.array(lst_a)  # arrayに変換
diff = ar_lst_q != ar_lst_a # 配列を一括比較 -> 要素同士の比較結果が配列で格納される
result = np.sum(diff)

上記は、ふたつの文字列が同じ長さだから可能なものです。長さが異なる場合は適用できません。

Comments

[opyon]

ありがとうございます。
恐らく環境的な問題でnumpy絡みのエラーが出ているので解決次第確認します。

[hayataka2049]

実測した感じ、100文字以上くらいならその方が速そうです
↑計測ミスがあったので訂正、かなり長い文字列でも素直にループした方が早かったです

[R.Shigemori]

numpyって意外と遅いんですね。

じゃぁ、import cupy as npにしたら…
って、それでは環境が違いすぎますね。

[hayataka2049]

numpyが遅い速いというより、この手の文字列処理では恩恵を受けられないと言うだけの話な気がします
あと素のpythonが意外と優秀なときは優秀

[opyon]

https://gyazo.com/7de0225ffa5ff7b4248b91efb5c7cd58
numpyのエラーが解決してやっと検証出来ました。
今回の例では遅いようです。
使い所次第で良い結果が出ることもあるかもしれません。
numpyを使ったことがあまりないのでどのように使うかも今後の課題です。