avoiding nested for loops python

Question

I have a function which takes in expressions and replaces the variables with all the permutations of the values that I am using as inputs. This is my code that I have tested and works, however after looking through SO, people have said that nested for loops are a bad idea however I am unsure as to how to make this more efficient. Could somebody help? Thanks.

def replaceVar(expression):

    eval_list = list()

    a = [1, 8, 12, 13]
    b = [1, 2, 3, 4]
    c = [5, 9, 2, 7]

    for i in expression:
        first_eval = [i.replace("a", str(j)) for j in a]
        tmp = list()
        for k in first_eval:
            snd_eval = [k.replace("b", str(l)) for l in b]
            tmp2 = list()
            for m in snd_eval:
                trd_eval = [m.replace("c", str(n)) for n in c]
                tmp2.append(trd_eval)
            tmp.append(tmp2)
        eval_list.append(tmp)
    print(eval_list)
    return eval_list

print(replaceVar(['b-16+(c-(a+11))', 'a-(c-5)+a-b-10']))

Solution 1

Foreword

Nested loops are not a bad thing per se. They are only bad, if there are used for problems, for which better algorithm have been found (better and bad in terms of efficiency regarding the input size). Sorting of a list of integers for example is such a problem.

Analyzing the Problem

The size

In your case above you have three lists, all of size 4. This makes 4 * 4 * 4 = 64 possible combinations of them, if a comes always before b and b before c. So you need at least 64 iterations!

Your approach

In your approach we have 4 iterations for each possible value of a, 4 iterations for each possible value of b and the same for c. So we have 4 * 4 * 4 = 64 iterations in total. So in fact your solution is quite good! As there is no faster way of listening all combinations, your way is also the best one.

The style

Regarding the style one can say that you can improve your code by better variable names and combining some of the for loops. E.g. like that:

def replaceVar(expressions):
    """
    Takes a list of expressions and returns a list of expressions with
    evaluated variables.
    """
    evaluatedExpressions = list()

    valuesOfA = [1, 8, 12, 13]
    valuesOfB = [1, 2, 3, 4]
    valuesOfC = [5, 9, 2, 7]

    for expression in expressions:
        for valueOfA in valuesOfA:
            for valueOfB in valuesOfB:
                for valueOfC in valuesOfC:
                    newExpression = expression.\
                                    replace('a', str(valueOfA)).\
                                    replace('b', str(valueOfB)).\
                                    replace('c', str(valueOfC))
                    evaluatedExpressions.append(newExpression)

    print(evaluatedExpressions)
    return evaluatedExpressions

print(replaceVar(['b-16+(c-(a+11))', 'a-(c-5)+a-b-10']))

Notice however that the amount of iterations remain the same!

Itertools

As Kevin noticed, you could also use itertools to generate the cartesian product. Internally it will do the same as what you did with the combined for loops:

import itertools

def replaceVar(expressions):
    """
    Takes a list of expressions and returns a list of expressions with
    evaluated variables.
    """
    evaluatedExpressions = list()

    valuesOfA = [1, 8, 12, 13]
    valuesOfB = [1, 2, 3, 4]
    valuesOfC = [5, 9, 2, 7]

    for expression in expressions:
        for values in itertools.product(valuesOfA, valuesOfB, valuesOfC):
            valueOfA = values[0]
            valueOfB = values[1]
            valueOfC = values[2]
            newExpression = expression.\
                            replace('a', str(valueOfA)).\
                            replace('b', str(valueOfB)).\
                            replace('c', str(valueOfC))
            evaluatedExpressions.append(newExpression)

    print(evaluatedExpressions)
    return evaluatedExpressions

print(replaceVar(['b-16+(c-(a+11))', 'a-(c-5)+a-b-10']))

Solution 2

here are some ideas:

1. as yours list a, b and c are hardcoded, harcode them as strings, therefore you don't have to cast every element to string at each step

2. use list comprehension, they are a little more faster than a normal for-loop with append

3. instead of .replace, use .format, it does all the replace for you in a single step

4. use itertools.product to combine a, b and c

with all that, I arrive to this

import itertools

def replaceVar(expression):

    a = ['1', '8', '12', '13' ]
    b = ['1', '2', '3', '4' ]
    c = ['5', '9', '2', '7' ]
    expression = [exp.replace('a','{0}').replace('b','{1}').replace('c','{2}') 
                  for exp in expression] #prepare the expresion so they can be used with format

    return [ exp.format(*arg) for exp in expression  for arg in itertools.product(a,b,c) ]

the speed gain is marginal, but is something, in my machine it goes from 148 milliseconds to 125

Functionality is the same to the version of R.Q.

Solution 3

"The problem" with nested loops is basically just that the number of levels is hard coded. You wrote nesting for 3 variables. What if you only have 2? What if it jumps to 5? Then you need non-trivial surgery on the code. That's why itertools.product() is recommended.

Relatedly, all suggestions so far hard-code the number of replace() calls. Same "problem": if you don't have exactly 3 variables, the replacement code has to be modified.

Instead of doing that, think about a cleaner way to do the replacements. For example, suppose your input string were:

s = '{b}-16+({c}-({a}+11))'

instead of:

'b-16+(c-(a+11))'

That is, the variables to be replaced are enclosed in curly braces. Then Python can do all the substitutions "at once" for you:

>>> s.format(a=333, b=444, c=555)
'444-16+(555-(333+11))'

That hard-codes the names and number of names too, but the same thing can be accomplished with a dict:

>>> d = dict(zip(["a", "b", "c"], (333, 444, 555)))
>>> s.format(**d)
'444-16+(555-(333+11))'

Now nothing about the number of variables, or their names, is hard-coded in the format() call.

The tuple of values ((333, 444, 555)) is exactly the kind of thing itertools.product() returns. The list of variable names (["a", "b", "c"]) can be created just once at the top, or even passed in to the function.

You just need a bit of code to transform your input expressions to enclose the variable names in curly braces.

Solution 4

So, your current structure addresses one of the inefficiencies that the solutions with itertools.product will not address. Your code is saving the intermediately substituted expressions and reusing them, rather than redoing these substitutions with each itertools.product tuple. This is good and I think your current code is efficient.

However, it is brittle and only works when substituting in exactly three variables. A dynamic programming approach can solve this issue. To do so, I'm going to slightly alter the input parameters. The function will use two inputs:

expressions - The expressions to be substituted into

replacement_map - A dictionary which provides the values to substitute for each variable

The dynamic programming function is given below:

def replace_variable(expressions, replacement_map):
    return [list(_replace_variable([e], replacement_map)) for e in expressions]

def _replace_variable(expressions, replacement_map):
    if not replacement_map:
        for e in expressions:
            yield e
    else:
        map_copy = replacement_map.copy()
        key, value_list = map_copy.popitem()
        for value in value_list:
            substituted = [e.replace(key, value) for e in expressions]
            for e in _replace_variable(substituted, map_copy):
                yield e

With the example usage:

expressions = ['a+b', 'a-b']

replacement_map = {
    'a': ['1', '2'],
    'b': ['3', '4']
}

print replace_variable(expressions, replacement_map)
# [['1+3', '1+4', '2+3', '2+4'], ['1-3', '1-4', '2-3', '2-4']]

Note that if you're using Python 3.X, you can use the yield from iterator construct instead of reiterating over e twice in _replace_variables. This function would look like:

def _replace_variable(expressions, replacement_map):
    if not replacement_map:
        yield from expressions

    else:
        map_copy = replacement_map.copy()
        key, value_list = map_copy.popitem()
        for value in value_list:
            substituted = [e.replace(key, value) for e in expressions]
            yield from _replace_variable(substituted, map_copy)

View more solutions

Comments

[Kevin]

itertools.product might be useful here.

[R. Q.]

@carl saptarshi: Did any of the answers below helped you? Please remember to mark the one which helped you as the accepted answer or otherwise explain why none of them helped you.

[R. Q.]

Can you mark it as the accepted answer then please :-)