Como ejemplo de cómo utilizar la memoria para aumentar el rendimiento de un algoritmo, lo siguiente se ejecuta aproximadamente veces más rápido para este caso de prueba en particular. Antes, tomaba ~ 200 segundos; 2/3 memoized.
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 old_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 = old_search(a_pref, b_pref)
# Create suffix tree to search.
a_suff, b_suff = a[a_term:], b[b_term:]
s_tree = old_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)
################################################################################
def search(memo, 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.
key = a_pref, b_pref = a[:a_addr], b[:b_addr]
if key not in memo:
memo[key] = search(memo, a_pref, b_pref)
p_tree = memo[key]
# Create suffix tree to search.
key = a_suff, b_suff = a[a_term:], b[b_term:]
if key not in memo:
memo[key] = search(memo, a_suff, b_suff)
s_tree = memo[key]
# 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)
################################################################################
import time
a = tuple(range(50))
b = (48, 11, 5, 22, 28, 31, 14, 18, 7, 29, 49, 44, 47, 36, 25, 27,
34, 10, 38, 15, 21, 16, 35, 20, 45, 2, 37, 33, 6, 30, 0, 8, 13,
43, 32, 1, 40, 26, 24, 42, 39, 9, 12, 17, 46, 4, 23, 3, 19, 41)
start = time.clock()
old_search(a, b)
stop = time.clock()
print('old_search() =', stop - start)
start = time.clock()
search({}, a, b)
stop = time.clock()
print('search() =', stop - start)
Referencia:How can memoization be applied to this algorithm?
no es en absoluto difícil de ver su valor. – hop
posible duplicado de [¿Qué es la memorización?] (Http://stackoverflow.com/questions/1988804/what-is-memoization) –