Efficiency considerations: nested loop vs recursion

Question

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 = [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 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 ################
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):
    pass

subtract = lambda x,y: x-y
def add(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
add.display_string = '+'
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[0],'=',target_expressions[0].value)
    print()
    print ("Took",time.time()-start_time,"seconds.")
    print(target_expressions)
    print(count)

Answer 1

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.

Answer 2

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

def ordered_add(num1,num2):
    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)