Reduce running time in Python simulation

Asked

Viewed 64 times

0

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!

1 answer

2


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.

  • Got it, Thank you very much!!

  • @Diegon If this answer solved your problem and you have no further questions, click the " " on the left of the answer to mark it as accepted/correct, which also marks your question as solved/answered. Otherwise, feel free to comment.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.