ハッシュテーブルを使用した最も長い一般的なサブシーケンスアルゴリズムを見つける

Question

最も長い一般的なサブシーケンスを見つけるために、アルゴリズムを設計しました。これらはステップです：

から始まります i = 0

1. ITH文字から最初の文字列開始から最初の文字を選択します。
2. その選んだ文字を探して、2番目の文字列に移動します。
3. 発見されていない場合は、最初の文字列に戻り、次の文字を選択し、2番目の文字列にある文字が見つかるまで1〜3を繰り返します。
4. 2番目の文字列に共通の文字が見つかったので、それを追加します $common_subsequence.
5. その位置をに保存します $index.
6. 最初の文字列から次の文字を選択し、ステップ2を実行しますが、今回はから始まります $index.
7. 文字列1または文字列2の終わりに達するまで3〜6を繰り返します。
8. 長さの場合 $common_subsequence これまでのところ、一般的なサブシーケンスの長さよりも大きいことは、LCSを変更する $common_subsequence.
9. iに1を追加し、1〜9を繰り返しますが、最初の文字列の長さが少なくなります。

これは例です：
‫‪

X=A, B, C, B, D, A, B‬‬  
‫‪Y=B, D, C, A, B, A‬‬ 

1. 最初のピック A.
2. 探す A の Y.
3. 今それが見つかりました A それを追加します $common_subsequence.
4. 次に、選択します B から X.
5. 探す B の Y しかし、今回はからの検索を開始します A.
6. 今選んでください C. 。文字列2にはありませんので、次の手紙を選択してください X あれは B.
   ...
   ...
   ...

このアルゴリズムの複雑さはシータ（n*m）です。

2つの方法で実装しました。 2つ目はハッシュテーブルを使用しますが、実装後、最初のアルゴリズムと比較してはるかに遅いことがわかりました。私は理由を非表示にすることができません。

これが私の実装です：

最初のアルゴリズム：

import time
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if string is empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        start = 0 # start position in ystr
        for item in xstr[i:]:
            index = ystr.find(item, start) # position at the common letter
            if index != -1: # if common letter has found
                cs += item # add common letter to the cs
                start = index + 1
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs) 
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

ハッシュテーブルを使用して2番目のもの：

import time
from collections import defaultdict
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if strings are empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    location = defaultdict(list) # keeps track of items in the ystr
    i = 0
    for k in ystr:
        location[k].append(i)
        i += 1
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        index = -1
        reached_index = defaultdict(int)
        for item in xstr[i:]:
            for new_index in location[item][reached_index[item]:]:
                reached_index[item] += 1
                if index < new_index:
                    cs += item # add item to the cs
                    index = new_index
                    break
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs) 
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

Answer 1

最適化の1つは、アクセスを置き換えることです reached_index[item] の開始時にハッシュテーブルから初期化されたローカル変数によって for item ループをループし、ループの端にあるハッシュテーブルに戻します。

物事をスピードアップするもう1つの最適化は、ハッシュテーブルをサイズ256の配列に置き換えることです。