1

問題は次のように実行されます。2つの文字列str1とstr2、および別の文字列がある場合、元のシーケンスと同じシーケンスに' s文字と's文字の両方が含まれてstr3いるかどうかをチェックする関数を記述します。したがって、adbfecは、部分文字列adfおよびbecに対してtrueを返します。私はPythonで次の関数を書きました：str3str1str2

def isinter(str1,str2,str3):
    p1,p2,p3 = 0,0,0
    while p3 < len(str3):
        if p1 < len(str1) and str3[p3] == str1[p1]:
            p1 += 1
        elif p2 < len(str2) and str3[p3] == str2[p2]:
            p2 += 1
        else:
            break
        p3 = p1+p2
    return p3 == len(str3)

このプログラムの別のバージョンがardentart（最後の解決策）にあります。どちらが良いですか？私の考えでは、おそらく線形時間でそれを行うからです。それが良いかどうかにかかわらず、私のアルゴに最適化の余地はありますか？

4

4 に答える 4

2

残念ながら、ご使用のバージョンは機能しません。ab入力を想像してみてください ac、、acab。あなたのアルゴリズムはFalse正しくないものを返します。

str1問題は、で見られる文字str3が両方の方法で解釈できるときに常に歩くことです。str2歩く必要があるかもしれませんが、それはあなたのアルゴリズムで同等のチャンスを得ることはありません。

于 2012-09-23T22:40:00.753 に答える
1

これにアプローチする別の方法は、Pythonの正規表現モジュールreを使用することです。str1の文字を分割し、各文字を。*で囲んで、それらの間の任意の数（またはなし）の文字に一致させることができます。これにより、str1に一致するパターンが得られます。次に、str2についても同じことを行い、re.match（str1pattern、str3）とre.match（str2pattern、str3）を実行します。それらが両方ともオブジェクトを返す場合（つまり、None以外）、両方の文字列と一致します。

これは、チェックする文字列を追加するのが簡単で、他のさまざまな文字列で検索するためにより良いパフォーマンスが必要な場合は、パターンをコンパイルすることもできるため、おそらくより適切にスケーリングされます。

于 2012-09-23T22:24:33.637 に答える
1

リスト内の3つの文字列すべてを分割できます。

list1 = list(str1)

次に、list3現在使用しているのと同じアルゴリズムを使用して、がまたはに等しいかどうかを確認しlist3[i]ます。もしそうなら、あなたは適切なリストからアイテムを選びます。list1[0]list2[0]del

時期尚早のリストの終わりは、例外としてキャッチされる可能性があります。

アルゴリズムはまったく同じですが、実装のパフォーマンスが向上するはずです。

更新：実際にはそうではないことがわかりました（約2倍の時間）。まあ、知っておくと便利かもしれません。

そして、さまざまなシナリオのベンチマークを行っているときに、3つの文字列の長さが「正確」であると指定されていない限り（つまり、len（p1）+ len（p2）== len（p3））、最も効果的な最適化は次のようになります。最初に確認してください。これにより、文字列の長さが不適切なために2つの入力文字列が3番目の文字列と一致しないすべてのケースがすぐに破棄されます。

次に、両方の文字列に同じ文字が含まれている場合があり、それをlist1またはlist2に割り当てると、文字列の1つが一致しなくなる可能性があります。そのような場合、アルゴリズムはフォールスネガティブで失敗し、再帰が必要になります。

def isinter(str1,str2,str3,check=True):
    # print "Checking %s %s and %s" % (str1, str2, str3)
    p1,p2,p3 = 0,0,0
    if check:
        if len(str1)+len(str2) != len(str3):
            return False
    while p3 < len(str3):
        if p1 < len(str1) and str3[p3] == str1[p1]:
            if p2 < len(str2) and str3[p3] == str2[p2]:
                # does str3[p3] belong to str1 or str2?
                if True == isinter(str1[p1+1:], str2[p2:], str3[p3+1:], False):
                   return True
                if True == isinter(str1[p1:], str2[p2+1:], str3[p3+1:], False):
                   return True
                return False
            p1 += 1
        elif p2 < len(str2) and str3[p3] == str2[p2]:
            p2 += 1
        else:
            return False
        p3 += 1
    return p1 == len(str1) and p2 == len(str2) and p3 == len(str3)

次に、ランダムな文字列でいくつかのベンチマークを実行しました。これはインストルメンテーションです（常に有効なシャッフルが生成されるため、偏った結果が生じる可能性があります）。

for j in range(3, 50):
        str1 = ''
        str2 = ''
        for k in range(1, j):
                if random.choice([True, False]):
                        str1 += chr(random.randint(97, 122))
                if random.choice([True, False]):
                        str2 += chr(random.randint(97, 122))
        p1 = 0
        p2 = 0
        str3 = ''
        while len(str3) < len(str1)+len(str2):
                if p1 < len(str1) and random.choice([True, False]):
                        str3 += str1[p1]
                        p1 += 1
                if p2 < len(str2) and random.choice([True, False]):
                        str3 += str2[p2]
                        p2 += 1
        a = time.time()
        for i in range(1000000):
                isShuffle2(str1, str2, str3)
        a = (time.time() - a)
        b = time.time()
        for i in range(1000000):
                isinter(str1, str2, str3)
        b = (time.time() - b)

        print "(%s,%s = %s) in %f against %f us" % (str1, str2, str3, a, b)

結果は、短い文字列に対するcached+DPアルゴリズムの優れた効率を示しているようです。文字列が長くなると（3〜4文字を超える）、cache+DPアルゴリズムは機能を失い始めます。長さが約10の場合、上記のアルゴリズムは、完全に再帰的なキャッシュバージョンの2倍の速度で実行されます。

文字列に繰り返し文字が含まれている場合（azからaiまでの範囲を制限することでこれを行った）、オーバーラップがわずかである場合、DPアルゴリズムのパフォーマンスは向上しますが、それでも上記のアルゴリズムよりも劣ります。たとえば、この場合、DPは2usだけ負けます。

(cfccha,ddehhg = cfcchaddehhg) in 68.139601 against 66.826320 us

当然のことながら、完全なオーバーラップ（各文字列から順番に1文字）では、364：178（2：1より少し大きい）の比率で、より大きな違いが見られます。

于 2012-09-23T22:27:20.833 に答える
0

まず、実装のポイントです。str1とstr2の長さのテストを取り除くことができると思います。Cでは、文字列はヌル文字で終了するため、この特殊文字はstr3では検出されません。だからp1++、正しい文字を見つけたら入れてください。しかし、Pythonでは、この機能が有効かどうかは覚えていません...申し訳ありませんが、私は真面目なPythonユーザーではありません。p1 == len（p1）の場合、str1 [p1]の出力はどうなりますか？

これに加えて、Jirka Hanikaが指摘しているように、コードの出力が間違っています。私はそれが失敗する別の状況を見てきました：文字が両方の部分文字列と共通である場合。例：str1 = "abc"、str2 = "dbe"の場合、str3 = "adbec"にはstr1とstr2の両方が含まれますが、この場合、アルゴリズムは失敗します。問題はelifステートメントから来ています、代わりに別のifを入れてください。

Iserniによるコードの出力は、私には正しいもののようです。

于 2012-09-24T08:57:45.397 に答える