Как memoization может быть применен к этому алгоритму?
После нахождения difflib.SequenceMatcher класс в стандартной библиотеке Python, чтобы быть неподходящим для моих потребностей, универсальной "разности" - модуль луга был записан для решения пространства задач. После наличия нескольких месяцев для размышления больше о том, что это делает рекурсивный алгоритм, кажется, ищет больше, чем в потребностях к путем исследования тех же областей в последовательности, которую, возможно, также исследовал отдельный "поисковый поток".
Цель diff модуль должен вычислить различие и общие черты между парой последовательностей (список, кортеж, строка, байты, bytearray, и так далее). Начальная версия была намного медленнее, чем текущая форма кода, видя, что скорость увеличивается фактором десять. Как memoization может быть применен к следующему коду? Что лучший способ состоит в том, чтобы переписать алгоритм для дальнейшего увеличения возможной скорости?
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)
Ссылка: Как оптимизировать рекурсивный алгоритм для не повторений?
2 ответа
Как сказал ~unutbu, попробуйте memoized decorator и следующие изменения:
@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)
Для memoization лучше всего подходят словари, но они не могут быть нарезаны, поэтому их нужно изменить на списки, как указано в комментариях выше.
Вы можете использовать декоратор memoize из библиотеки Python Decorator Library и используйте его так:
@memoized
def search(a, b):
При первом вызове search с аргументами a, b результат вычисляется и запоминается (сохраняется в кэше). Второй раз поиск вызывается с теми же аргументами, результат возвращается из кеша.
Обратите внимание, что для работы мемоизированного декоратора аргументы должны быть хешируемыми. Если a и b являются наборами чисел, то они хешируемые. Если это списки, вы можете преобразовать их в кортежи перед передачей в поиск .
Не похоже, что search принимает dicts в качестве аргументов, но если бы они были, то они не были бы хешируемыми , и декоратор мемоизации не смог бы сохранить результат в кеш.