Reduce Runtime Python3

Question

I’m solving a challenge here, which is to basically see how many elements of a list fit into ALL ranges of an array.

And my solution was this:

def countSignals(frequencies, filterRanges):
    corretos = 0
    len_fR = len(filterRanges)
    for i in frequencies:
        for a in range(len_fR):
            if i in range(filterRanges[a][0], filterRanges[a][1] + 1):
                passou = True
                if passou and filterRanges[a] == filterRanges[-1]:
                    corretos+=1
            else:
                 break
    return corretos


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

How the execution works:

I receive a number, which will be equivalent to Len(Frequencies). Then I receive each of the elements that will make up the Frequencies list. Then I get the value of Len(filterRanges). Then I get the dimension of each of the lists that make up filterRanges At the end, I get the values of each of the lists.

Example of input:

5 #-> len(frequencies)
20 #-> frequencies[0]
5 #-> frequencies[1]
6 #-> frequencies[2]
7 #-> frequencies[3]
12# -> frequencies[4]
3 #-> len(filterRanges), sendo que este é composto por listas
2 #-> tamanho das listas que compõe filterRanges
10 20 #-> filterRanges[0] = [10,20]
5 15 #-> filterRanges[1] = [5,15]
5 30 #-> filterRanges[2] = [5,30]

The code needs to count how many frequency values are in the range of ALL lists that make up filterRanges.

In this case, for example, the return would be 1, because only the number 12 fits in all ranges.

He passed 10 of the 15 tests, and the other 5 gave timeout. Does anyone have any suggestions to optimize the code? The error that gave was "Terminated due to timeout", because the code was running for more than 10 seconds (it gives timeout qunado arrives in 10). How do I optimize this code?

EDIT AFTER SUGGESTIONS:

def countSignals(frequencies, ranges):
    ranges = [range(i[0], i[1] + 1) for i in ranges]
    return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

I passed 12/15 tests. I need to optimize more... I can’t change anything defined in the main method, I can only change the countSignals function.

Answer 1

Some tips:

At least in Python IDLE, you don’t need to use the method strip in function input, since pressing enter the character '\n' is not taken into account. However if it is something that is not required in the competition, I recommend removing.

When reading the values of filterRanges, transform the values into an object range instead of a list.

for _ in range(filterRanges_rows):
    ini, fin = (int(i) for i in input().split(' '))
    filterRanges.append(range(ini, fin+1))

The function countSignals you can do on a line:

def countSignals(frequencies, ranges):
    return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)

Split:

f in r
# verifica se f está em r

f in r for r in ranges
# retorna um iterável de booleanos onde cada elemento
# indica se f está em r para cada r na lista ranges

all(f in r for r in ranges)
# verifica se todos os elementos desse
# iterável são verdadeiros (True), ou seja,
# se a frequência f está em todos os
# intervalos da lista ranges

1 if all(f in r for r in ranges) else 0
# retorna 1 se todos os elementos do iterável
# são verdadeiros, senão retorna 0

1 if all(f in r for r in ranges) else 0 for f in frequencies
# repete essa operação para todas as frequencias

sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)
# soma todos os elementos que possuem 1
# ou seja, a quantidade de frequencias que
# estão em todos os intervalos da lista ranges

See if these tips improve your code execution time.

EDIT: Haha, I’m sorry, I didn’t know that part of main was predefined by the platform. You can go modifying some function factors countSignals and seeing the result:

Try to use generating expressions rather than understanding lists when creating objects range in the first line of the function, where

ranges = [range(r[0], r[1] + 1) for r in ranges]

becomes

ranges = (range(r[0], r[1] + 1) for r in ranges)

Try to replace the use of objects range by comparing the elements in the list itself ranges, where

ranges = [range(r[0], r[1] + 1) for r in ranges]
return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)

becomes

return sum(1 if all(f >= r[0] and f <= r[1] for r in ranges) else 0 for f in frequencies)

You can also remove the use of else 0 since it does not interfere with the function sum.

return sum(1 for f in frequencies if all(f >= r[0] and f <= r[1] for r in ranges))