I have an algorithm that constructs an optimal binary tree using dynamic programming. After introducing what I thought would be an optimization, the algorithm became over 2 times slover. Question: Is there an analytical way to determine whether such change will improve the runtime of an algorithm with memoization?
Python code and description follow:
def solver(problem, memo={}):
try:
return memo[problem]
except KeyError:
if is_base_case(problem):
memo[problem] = base_solver(problem)
return memo[problem]
best_score, best_solution = INFINITY, None
for left_subproblem, right_subproblem in all_splits(problem):
left_solution = solver(left_subproblem, memo)
if (base_score(problem) + score(left_solution) >= best_score): #optimization
continue #optimization
right_solution = solver(right_subproblem, memo)
current_score = base_score(problem) + score(left_solution) + score(right_solution)
if (current_score < best_score):
best_score = current_score
best_solution = combine_solutions(problem, left_solution, right_solution)
memo[problem] = best_solution
return memo[problem]
The function iterates over all ways to split an instance problem into two subproblems, recursively solves them and stores the solutions.
Optimal tree is a tree that has the lowest score, determined by the score()
function. The score of a tree is always positive and is a sum of a base score of the root node plus the score of the subtrees.
The optimization in question are the lines marked as #optimization
. It's supposed to avoid solving the right subproblem, if, based on the left result, it's impossible to create a solution with a better score than the current best.
Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work. However, this is just my hindsight and I would like to have a rigorous way to analyse the problem, in case an algorithm like this was presented to me in pseudo-code.