Efficiency considerations: nested loop vs recursion

I would consider myself an intermediate Python programmer. One of my recent challenges was creating a list of all possible solutions to a given Countdown problem. Without getting into too much detail, I have approached the problem through:

• first generating a list of all possible Number-Operator arrangements using RPN

• and then bruteforcing all possible permutations numbers/operators for all possible arrangements, recording the patterns that give me the answer.

The full code listing is further below.

I am aware that this is utterly inefficient and my program takes on the scale of 5-10 minutes to complete.

I have come across an alternative approach here, which uses recursion and generators and finishes considerably faster - on the scale of 30 seconds. My level of understanding of Python does not allow me to just read through the code I found and fully understand the nuances.

I understand that it recursively creates branched expressions with all possible permutations and evaluates them until the correct result is reached, which is essentially another take of what I am doing. I do not understand why that code is orders of magnitude faster than mine.

Operations-wise, the faster code makes on the scale of 5 million attempts, mine makes 15 million attempts, but that still does not match up to the difference in time of execution.

My question: I would be very grateful for a pointer as to what exactly about the class/recursion approach makes it this much more efficient than my rather naive approach to basically the same method.

After tinkering with switching off various modules in the nested loop, I think I narrowed it down. I think, quite disappointingly, that the slowest part is the way I evaluate RPN expressions.

What I did:

• Replaced the line result = RPN_eval(...) with result = . This completes the program in under 9 seconds.

• I then restored the line back to call the RPN_eval(...) function. Instead, I got rid of the attempt string generation and replaced it with a fixed 2 2 + - this version terminated in under 69 seconds...

• Finally, fixing attempt to be 2 2 + 2 + increased the running time to 120 seconds.

Extrapolating (roughly) this finding that each additional number and operator in the expression increases the program time by a factor of around 1.7 - I get total run time of 10-11 minutes, which is what my program shows under normal conditions.

My new question: Therefore, what is the part of the RPN_eval function that seems to be so awkward and slow? Will do more research and formalise this into an actual separate question, not relevant here as such

I think I am onto something - I am trying to dynamically convert RPN pattern expressions into a (horrendous) lambda function, that I can then feed individual number permutations to and yield outcomes, without having to remake the lambda function until the next pattern kicks in. Will add code here once it cooperates...

My code listing:

import itertools as it
import random
import time
operators = ["+", "-", "/", "*"]
count = 0

def RPN_eval(expression, answer): #a standard stack approach to evaluating RPN expressions
explist = expression.split(" ")
explist.pop(-1)
stack = []

for char in explist:

if not char in operators:
stack.append(int(char))
else:
if char == "+":
num1 = stack.pop()
num2 = stack.pop()

if num1 > num2:
return[-1]

result = num1 + num2
stack.append(result)

if char == "-":
num1 = stack.pop()
num2 = stack.pop()
result = -num1 + num2
stack.append(result)

if char == "*":
num1 = stack.pop()
num2 = stack.pop()

if num1 > num2:
return [-1]

result = num1 * num2
stack.append(result)

if char == "/":
divisor = stack.pop()
divident = stack.pop()

try:
result = divident / divisor
except:
return [-1]

stack.append(result)

if result<=0 or result != int(result):
return [-1]

return stack

################### This part runs once and generates 37 possible RPN patterns for 6 numbers and 5 operators
def generate_patterns(number_of_numbers):
#generates RPN patterns in the form NNoNNoo where N is number and o is operator

patterns = ["N "]

for pattern1 in patterns:
for pattern2 in patterns:
new_pattern = pattern1 + pattern2 + "o "
if new_pattern.count("N")<=number_of_numbers and new_pattern not in patterns:
patterns.append(new_pattern)

return patterns
#######################################

######### Slowest part of program ################
global count
patterns = generate_patterns(len(numbers)) #RPN symbolic patterns for a given number pool, runs once, takes less than 1 second
random.shuffle(patterns) #not necessary, but yields answers to look at faster on average
print(patterns)
solutions = [] #this list will store answer strings of good solutions. This particular input produces 56 answers.

for pattern in patterns:
nn = pattern.count("N") #counts the number of numbers in a symbolic pattern to produce corresponding number group permutations
no = pattern.count("o") #same for operators
numpermut = it.permutations(numbers,nn) #all possible permutations of input numbers, is an itertools.permutations object, not a list. Takes 0 seconds to define.

print(pattern)

for np in numpermut:
oppermut = it.product(["+","-","*","/"],repeat=no) #all possible permutations of operator order for a given pattern, itertools object, not a list. Takes 0 seconds to define
for op in oppermut:
attempt = ""
ni = 0
oi = 0
for sym in pattern:
if "N" in sym:
attempt+=str(np[ni])+" " #replace Ns in pattern with corresponding numbers from permutations
ni+=1
if "o" in sym:
attempt+=str(op[oi])+" " #replace os in pattern with corresponding operators from permutations
oi+=1

count+=1
result = RPN_eval(attempt, answer) #evaluate attempt

if result == answer:
solutions.append(attempt) #if correct, append to list

print(solutions)
return solutions
#####################################

solns = calculate_solutions([50 , 8 , 3 , 7 , 2 , 10],556)
print(len(solns), count)

And faster code listing:

class InvalidExpressionError(ValueError):
pass

subtract = lambda x,y: x-y
if x<=y: return x+y
raise InvalidExpressionError
def multiply(x,y):
if x<=y or x==1 or y==1: return x*y
raise InvalidExpressionError
def divide(x,y):
if not y or x%y or y==1:
raise InvalidExpressionError
return x/y

count = 0
multiply.display_string = '*'
subtract.display_string = '-'
divide.display_string = '/'

standard_operators = [ add, subtract, multiply, divide ]

class Expression(object): pass

class TerminalExpression(Expression):
def __init__(self,value,remaining_sources):
self.value = value
self.remaining_sources = remaining_sources
def __str__(self):
return str(self.value)
def __repr__(self):
return str(self.value)

class BranchedExpression(Expression):
def __init__(self,operator,lhs,rhs,remaining_sources):
self.operator = operator
self.lhs = lhs
self.rhs = rhs
self.value = operator(lhs.value,rhs.value)
self.remaining_sources = remaining_sources
def __str__(self):
return '('+str(self.lhs)+self.operator.display_string+str(self.rhs)+')'
def __repr__(self):
return self.__str__()

def ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0):
global count
for value, i in zip(sources,range(len(sources))):
yield TerminalExpression(value=value, remaining_sources=sources[:i]+sources[i+1:])
if len(sources)>=2+minimal_remaining_sources:
for lhs in ValidExpressions(sources,operators,minimal_remaining_sources+1):
for rhs in ValidExpressions(lhs.remaining_sources, operators, minimal_remaining_sources):
for f in operators:
try:
count+=1
yield BranchedExpression(operator=f, lhs=lhs, rhs=rhs, remaining_sources=rhs.remaining_sources)
except InvalidExpressionError: pass

def TargetExpressions(target,sources,operators=standard_operators):
for expression in ValidExpressions(sources,operators):
if expression.value==target:
yield expression

def FindFirstTarget(target,sources,operators=standard_operators):
for expression in ValidExpressions(sources,operators):
if expression.value==target:
return expression
raise (IndexError, "No matching expressions found")

if __name__=='__main__':
import time
start_time = time.time()
target_expressions = list(TargetExpressions(556,[50,8,3,7,2,10]))
#target_expressions.sort(lambda x,y:len(str(x))-len(str(y)))
print ("Found",len(target_expressions),"solutions, minimal string length was:")
print (target_expressions,'=',target_expressions.value)
print()
print ("Took",time.time()-start_time,"seconds.")
print(target_expressions)
print(count)
• The other algorithm must be doing less work. It is unlikely that the recursion is fundamental to it's better performance. You might try to put logging into each to see how they work. – Erik Eidt Jan 16 '17 at 16:05
• Your "progress update" should really be posted as an answer. This isn't a forum; we expect questions to be questions, answers to be answers, and dialog between community members to take place in comments, not in posts (posts don't even have support for @comments). – Robert Harvey Jan 17 '17 at 22:37
• @RobertHarvey Understood, thanks. Will get used to this. – IliaK Jan 17 '17 at 22:58

Let's walk though a few steps of the 'fast' solution:

TargetExpression is called with the problem. It calls ValidExpression which yields two iterators. The first iterator provides each TerminalExpression one at a time. The loop in TargetExpression checks each one to see if it is the answer if so, it is yielded (one at a time, via iterator) to the main program. Once done with that, it yields a second iterator which is returns candidate expressions one at a time by permuting through the possible using nested iterators. These values are again looped over by the loop in TargetExpression one at a time. Each of the nested iterators, will also only return one value at a time.

One difference here is that I think the 'fast' version pruning the calculations. That is, if the operands are out of order (i.e. first is not less than the second) it stops looking at any other results that start with those operands. For example, when it starts with 50 + 8, the fast version immediately bails and checks a different starting pair. If I'm not mistaken, your version will check all permutations that start with 50 + 8. It will ignore them but one at a time whereas the 'fast' version will disregard that entire part of the tree.

After your edit where you have a narrowed things down a bit, here are some thoughts on the RPN_eval method:

First, the easy stuff. You have a set of if statements which are mutually exclusive. You are going to check for all four operators on each loop even though only one of those checks will be true. You should change it to a chained if like so:

if not char in operators:
#...
elif char == "+":
#...
elif char == "-":
#...
elif char == "*":
#...
elif char == "/":

I'm not sure you need that last if statement but maybe I'm missing something. I doubt this will make a huge difference but it's more correctly conveying the intention and will be less prone to coding error.

The only thing this code does that looks at all expensive is the continual pushing and popping and that's not that costly. The best I can guess is that because you are checking the same operands more than the other versions that it adds up. This is for the same reason as described above for pruning. When the 'fast' version checks all the trees that start with 8 + 50, it does that operation one time. Your approach will do 2 pushes and 2 pops for every candidate tree that starts with 8 + 50. I don't have time to do that math but it's not a small number. You should try counting how many different expressions you calculate and how many start with the same root. It will likely be eye-opening.

• solns = calculate_solutions([50 , 8 , 3 , 7 , 2 , 10],556) this is the input in both cases, where 556 is the desired answer and the list is the number pool (last line in my code). I will edit my question to improve precision. – IliaK Jan 16 '17 at 16:43
• Sorry, I think you had it OK initially, I was focusing on the millions of trials and glossed over the details of the problem you are attempting to solve. – JimmyJames Jan 16 '17 at 16:51
• Thanks for the breakdown. You are slightly incorrect about my code, I think. I create a list of all patterns symbolically, which is 37 elements. The permutations of all possible numbers and operators for each pattern are iterators, I believe, created by using itertools (it.permutations(...) and it.product(...)). I use the for loops to step through each permutation to obtain an attempt, which is evaluated using my RPN parser, which then compares to a result. I only store two lists: solutions, which builds up to 56 for this problem, and patterns, which does not change after generation. – IliaK Jan 16 '17 at 17:20
• Right. I jut noticed that you are using itertools so that shouldn't be an issue. I'm looking at your code again... – JimmyJames Jan 16 '17 at 17:40
• I updated my answer with something hopefully not incorrect. – JimmyJames Jan 16 '17 at 18:00

Made an improvement on my RPN parser. The solution itself is still tailored quite narrowly to my specific problem, but the skills involved are, I think, very Pythonic and worthwhile. What I did in the end:

• Used each RPN pattern of form e.g. NNoNo and parsed it into a composite lambda function
• The composite function takes in two lists: a permutation of numbers to attempt and a permutation of symbols.
• Individual elements of the argument lists for the lambda are preallocated internally on lambda creation, so each number goes in its right place. Same for operators
• This defined composite function is used for all permutations for a given pattern, after which the function is re-defined for a new pattern. As there are only 37 patterns, I save some time on parsing and list manipulations.

Results are still underwhelming, but I will keep looking into it. On my desktop machine the dynamic function approach gives all results in 120 seconds vs 155 seconds for the previous approach.

Only the added functions are listed below:

import operator

def safe_division(num1,num2):
try:
r = num1/num2
if int(r) == r:
return r
else:
raise ValueError
except ZeroDivisionError:
raise ValueError

if num1>num2:
return num1+num2
else:
raise ValueError

def ordered_times(num1,num2):
if num1>num2:
return num1*num2
else:
raise ValueError

def positive_subtract(num1,num2):
if num1>=num2:
return num1-num2
else:
raise ValueError

ARITHMETIC_OPERATORS = {
'+':  ordered_add, '-':  operator.sub,
'*':  ordered_times, '/':  safe_division, '%':  operator.mod,
'**': operator.pow, '//': operator.floordiv,
}

def RPN_to_opexpression(pattern):
val = 0 #keeping track of which element in the permutation list to pass to the lambda
sym = 0 #same but for symbols
stack = []

for char in pattern:
if char == "N":
#if the character represents a Number, the "result" of this operation is a lambda that returns the number itself
stack.append(lambda symlist,vallist, val=val : vallist[val])
val+=1
else:
#if the character is an operator, the attached lambda is a composite of two previous stack contents composited over the operator
rhs = stack.pop()
lhs = stack.pop()
stack.append(lambda symlist,vallist, sym=sym, lhs=lhs, rhs=rhs: ARITHMETIC_OPERATORS[symlist[sym]](lhs(symlist,vallist),rhs(symlist,vallist)))
sym+=1
superfunction = stack.pop()

return superfunction

######################
#and in main body:
superfun = RPN_to_opexpression(pattern)
...
result = superfun(op,np)