0

Python の標準ライブラリのクラスが私のニーズに合わないことがわかった後difflib.SequenceMatcher、問題領域を解決するために一般的な「差分」モジュールが作成されました。再帰アルゴリズムは、何をしているのかをさらに考えるために数か月を費やした後、別の「検索スレッド」も調べた可能性のあるシーケンスで同じ領域を再検索することにより、必要以上に検索しているように見えます。

このモジュールの目的は、diff一連のシーケンス (リスト、タプル、文字列、バイト、bytearray など) の違いと類似性を計算することです。最初のバージョンは、コードの現在の形式よりもはるかに遅く、速度が 10 倍向上しました。次のコードにメモ化をどのように適用できますか? 可能な速度をさらに向上させるためにアルゴリズムを書き直す最良の方法は何ですか?

class Slice:

    __slots__ = 'prefix', 'root', 'suffix'

    def __init__(self, prefix, root, suffix):
        self.prefix = prefix
        self.root = root
        self.suffix = suffix

################################################################################

class Match:

    __slots__ = 'a', 'b', 'prefix', 'suffix', 'value'

    def __init__(self, a, b, prefix, suffix, value):
        self.a = a
        self.b = b
        self.prefix = prefix
        self.suffix = suffix
        self.value = value

################################################################################

class Tree:

    __slots__ = 'nodes', 'index', 'value'

    def __init__(self, nodes, index, value):
        self.nodes = nodes
        self.index = index
        self.value = value

################################################################################

def search(a, b):
    # Initialize startup variables.
    nodes, index = [], []
    a_size, b_size = len(a), len(b)
    # Begin to slice the sequences.
    for size in range(min(a_size, b_size), 0, -1):
        for a_addr in range(a_size - size + 1):
            # Slice "a" at address and end.
            a_term = a_addr + size
            a_root = a[a_addr:a_term]
            for b_addr in range(b_size - size + 1):
                # Slice "b" at address and end.
                b_term = b_addr + size
                b_root = b[b_addr:b_term]
                # Find out if slices are equal.
                if a_root == b_root:
                    # Create prefix tree to search.
                    a_pref, b_pref = a[:a_addr], b[:b_addr]
                    p_tree = search(a_pref, b_pref)
                    # Create suffix tree to search.
                    a_suff, b_suff = a[a_term:], b[b_term:]
                    s_tree = search(a_suff, b_suff)
                    # Make completed slice objects.
                    a_slic = Slice(a_pref, a_root, a_suff)
                    b_slic = Slice(b_pref, b_root, b_suff)
                    # Finish the match calculation.
                    value = size + p_tree.value + s_tree.value
                    match = Match(a_slic, b_slic, p_tree, s_tree, value)
                    # Append results to tree lists.
                    nodes.append(match)
                    index.append(value)
        # Return largest matches found.
        if nodes:
            return Tree(nodes, index, max(index))
    # Give caller null tree object.
    return Tree(nodes, index, 0)

参照: 再帰アルゴリズムを最適化して繰り返さないようにする方法は?

4

3 に答える 3

1

Python Decorator Libraryの memoize デコレータを次のように使用できます 。

@memoized
def search(a, b):

search引数を指定して初めて呼び出すとa,b、結果が計算されてメモ化されます (キャッシュに保存されます)。2 回目searchは同じ引数で呼び出され、結果はキャッシュから返されます。

memoizedデコレータが機能するには、引数がハッシュ可能でなければならないことに注意してください。aとbが数値のタプルである場合、それらはハッシュ可能です。それらがリストの場合は、それらを に渡す前にタプルに変換できますsearch。search引数として取るようには見えませんdictsが、もしそうなら、それらはハッシュ可能ではなく、メモ化デコレータは結果をキャッシュに保存できません。

于 2010-07-10T20:30:25.017 に答える
1

~unutbu が言ったように、メモ化されたデコレータと次の変更を試してください。

@memoized
def search(a, b):
    # Initialize startup variables.
    nodes, index = [], []
    a_size, b_size = len(a), len(b)
    # Begin to slice the sequences.
    for size in range(min(a_size, b_size), 0, -1):
        for a_addr in range(a_size - size + 1):
            # Slice "a" at address and end.
            a_term = a_addr + size
            a_root = list(a)[a_addr:a_term] #change to list
            for b_addr in range(b_size - size + 1):
                # Slice "b" at address and end.
                b_term = b_addr + size
                b_root = list(b)[b_addr:b_term] #change to list
                # Find out if slices are equal.
                if a_root == b_root:
                    # Create prefix tree to search.
                    a_pref, b_pref = list(a)[:a_addr], list(b)[:b_addr]
                    p_tree = search(a_pref, b_pref)
                    # Create suffix tree to search.
                    a_suff, b_suff = list(a)[a_term:], list(b)[b_term:]
                    s_tree = search(a_suff, b_suff)
                    # Make completed slice objects.
                    a_slic = Slice(a_pref, a_root, a_suff)
                    b_slic = Slice(b_pref, b_root, b_suff)
                    # Finish the match calculation.
                    value = size + p_tree.value + s_tree.value
                    match = Match(a_slic, b_slic, p_tree, s_tree, value)
                    # Append results to tree lists.
                    nodes.append(match)
                    index.append(value)
        # Return largest matches found.
        if nodes:
            return Tree(nodes, index, max(index))
    # Give caller null tree object.
    return Tree(nodes, index, 0)

メモ化には辞書が最適ですが、スライスできないため、上記のコメントに示されているようにリストに変更する必要があります。

于 2010-07-10T21:26:56.243 に答える