Reduce running time in Python simulation

Question

Hi. I’m trying to solve a problem where I have to create a function that receives a string of 0 and 1 and a list of commands, which can be 'I' and 'Q'. If it is 'I' the program must modify all values within the given limits and if it is 'Q' should add the specified widget to a list. For example:

binary_simulation("0011001100", [['I', 1, 10], ['I', 2, 7], ['Q', 2], ['Q', 1], ['Q', 7], ['Q', 5]])

That should bring us back: ['0','1','1','0']

It turns out I’ve already solved the problem, but it exceeds the time limit running the site. I was wondering if there was a way to reduce the execution time of my code. Follow him:

def binary_simulation(s, q):
    lst = []
    for e in q:
        if(e[0] == 'I'):
            for j in range(e[1]-1,e[2],1):
                if ( s[j] == '1'):
                    s = s[:j] + '0' + s[j+1:]
                else:
                    s = s[:j] + '1' + s[j+1:]
        else:
            lst.append(s[e[1]-1])
    return lst

Thank you, any help is welcome!

Answer 1

That operation:

s = s[:j] + '1' + s[j+1:]

This is something very slow. Basically it creates a whole new list by copying all the elements one by one and just swapping one of them in the middle. If there are 1,000,000 elements, doing it over and over will detonate your time.

Try something like that:

def binary_simulation(s, q):
    u = []
    for x in s:
        u.append(x)
    lst = []
    for e in q:
        if e[0] == 'I':
            for j in range(e[1] - 1, e[2]):
                u[j] = ('0' if u[j] == '1' else '1')
        else:
            lst.append(u[e[1] - 1])
    return lst

The idea is to use a list instead of a string (the variable u), because lists are mutable and therefore you can change them at will without having to rebuild a new one whenever you want to change an element.