3

入力の未知の領域をどれだけ正確に再構築できるかを確認するために、ランダムな文字列間の最長共通部分列を計算するこのコードがあります。良い統計を取得するには、何度も繰り返す必要がありますが、現在の Python の実装は遅すぎます。pypyを使用しても、現在 1 回の実行に 21 秒かかります。理想的には 100 回実行したいと考えています。

#!/usr/bin/python

import random
import itertools
#test to see how many different unknowns are compatible with a set of LCS answers.
def lcs(x, y):
    n = len(x)
    m = len(y)
#    table is the dynamic programming table
    table = [list(itertools.repeat(0, n+1)) for _ in xrange(m+1)]
    for i in range(n+1):     # i=0,1,...,n
        for j in range(m+1):  # j=0,1,...,m
            if i == 0 or j == 0:
                table[i][j] = 0
            elif x[i-1] == y[j-1]:
                table[i][j] = table[i-1][j-1] + 1
            else:
                table[i][j] = max(table[i-1][j], table[i][j-1])

    # Now, table[n, m] is the length of LCS of x and y.
    return table[n][m]

def lcses(pattern, text):
    return [lcs(pattern, text[i:i+2*l]) for i in xrange(0,l)]

l = 15
#Create the pattern
pattern = [random.choice('01') for i in xrange(2*l)]

#create text start and end and unknown. 
start = [random.choice('01') for i in xrange(l)]
end = [random.choice('01') for i in xrange(l)]
unknown = [random.choice('01') for i in xrange(l)]

lcslist= lcses(pattern, start+unknown+end)

count = 0
for test in itertools.product('01',repeat = l):
    test=list(test)
    testlist = lcses(pattern, start+test+end)
    if (testlist == lcslist):
        count += 1

print count

私はそれをnumpyに変換しようとしましたが、実際にはもっと遅く実行されたので、うまくいかなかったに違いありません. このコードはどうにかして高速化できますか?

アップデート。以下のコメントに従って、と同じ長さのすべてのサブリストのlcses間に LCS を与える再帰を直接使用した方がよいでしょう。これを行うために、古典的な動的計画法 LCS アルゴリズムを何らかの方法で変更することは可能ですか?patterntext

4

1 に答える 1

1

再帰テーブルは、 when it is only 依存し、whereの最大値は であり、最大値は であるへのtable呼び出しごとに 15 回再計算されています。lcses()mnm2*ln3*l

あなたのプログラムが一度だけテーブルを計算した場合、それは現在そうではない動的プログラミングになります。これに対する Python のイディオムは次のようになります。

table = None
def use_lcs_table(m, n, l):
    global table
    if table is None:
        table = lcs(2*l, 3*l)
    return table[m][n]

ただし、クラス インスタンスを使用すると、グローバル テーブル宣言よりもクリーンで拡張性が高くなります。しかし、これにより、なぜそんなに時間がかかるのかがわかります。

コメントへの返信として追加:

動的計画法は、時間の短縮と余分なスペースのトレードオフを必要とする最適化です。あなたの例では、テーブルの事前計算を行っているように見えますがlcs()、すべての呼び出しでリスト全体を作成してから破棄します。実装しようとしているアルゴリズムを理解しているとは言いませんが、コーディング方法は次のいずれかです。

  1. 再帰関係がないため、DP 最適化の根拠がない、または
  2. 再帰関係があり、その実装は失敗しました。
于 2013-06-29T16:01:45.067 に答える