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 RPNand 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 = [0]. 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 suchI 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 itimport randomimport timeoperators = [+, -, /, *]count = 0def 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 operatorsdef 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 ################def calculate_solutions(numbers, answer):    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[0] == 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):    passsubtract = lambda x,y: x-ydef add(x,y):    if x<=y: return x+y    raise InvalidExpressionErrordef multiply(x,y):    if x<=y or x==1 or y==1: return x*y    raise InvalidExpressionErrordef divide(x,y):    if not y or x%y or y==1:        raise InvalidExpressionError    return x/ycount = 0add.display_string = '+'multiply.display_string = '*'subtract.display_string = '-'divide.display_string = '/'standard_operators = [ add, subtract, multiply, divide ]class Expression(object): passclass 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: passdef TargetExpressions(target,sources,operators=standard_operators):    for expression in ValidExpressions(sources,operators):        if expression.value==target:            yield expressiondef 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[0],'=',target_expressions[0].value)    print()    print (Took,time.time()-start_time,seconds.)    print(target_expressions)    print(count)
Efficiency considerations: nested loop vs recursion
algorithms;python;performance;recursion;loops
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.